算法提高模板强连通分量tarjan算法

AC代码：

#include

using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int N = 2e5 + 10;

//强联通分量模板
//tarjan算法
vector<int>e[N];
int n, m, cnt;
int dfn[N], low[N], ins[N], idx;
int bel[N];//记录每个点在哪一个强连通分量里
stack<int>stk;
vector<vector<int>>scc;
void tarjan(int u)
{
	dfn[u] = low[u] = ++ idx;//时间戳；
	ins[u] = true;//有没有被切掉
	
	stk.push(u);
	for(auto v : e[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else 
		{
			if(ins[v]) low[u] = min(low[u], dfn[v]);
		}
	}
	if(dfn[u] == low[u])//一个强连通分量
	{
		vector<int>c;
		++cnt;//记录每个点到底在哪一个连通块里
		while(1){
			int v = stk.top();
			bel[v] = cnt;
			c.push_back(v);
			stk.pop();
			if(v == u) break;
		}
		sort(c.begin(), c.end());//题目要求字典序
		scc.push_back(c);//存下来每一个连通块
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
	}//有向边
	for(int i = 1; i <= n; i ++)
	{
		if(!dfn[i]) tarjan(i);
	}
	sort(scc.begin(), scc.end());
	for(auto it : scc)
	{
		for(auto c : it)
		{
			cout << c << " ";
		}
		cout << endl;
	}
}

受欢迎的牛：

带注释的代码：

#include

using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int N = 2e5 + 10;

//tarjan
vector<int>e[N];
int n, m, cnt;//cnt代表强连通分量的总数
int dfn[N];//记录时间戳；
int low[N];//记录每个连通块内的最小节点
int ins[N];//记录有没有被切割掉
int idx;//时间戳的标号
int bel[N];//记录每个点在哪一个强联通分量里
stack<int>stk;//储存每个强连通块的点
vector<vector<int>>scc;//储存每个强连通块
int outd[N];//储存每个强连通块的出度
int sz[N];//第i个强联通块的点数

void  tarjan(int u)
{
	dfn[u] = low[u] = ++ idx;//记录时间戳
	ins[u] = 1;//记录遍历过了
	stk.push(u);//存点
	for(auto v : e[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else
		{
			if(ins[v])
			low[u] = min(low[u], dfn[v]);//记录连通块内的最小点，方便辨认是不是同一个连通块
		}
	}
	if(dfn[u] == low[u])
	{
		vector<int>c;//存每一个连通块的小数组
		++ cnt;//连通块的下标
		while(1){
			int v = stk.top();
			bel[v] = cnt;//记录每个点到底在哪一个连通块内
			sz[cnt] ++;//每个联通块点的数量
			c.push_back(v);
			stk.pop();
			if(u == v) break;//说明遍历完了该连通块
		}
		sort(c.begin(), c.end());//题目要求
		scc.push_back(c);//存下每个连通块
	}
}
int main()
{
	cin >> n >> m;//输入
	for(int i = 1; i <= m; i ++)
	{
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);//输入有向边
	}
	for(int i = 1; i <= n; i ++)
	{
		if(!dfn[i]) tarjan(i);//对每一个点进行讨论，相当于求连通块然后在这部进行操作罢了
	}
	sort(scc.begin(), scc.end());//题目说按照最小字典序
	for(int u = 1; u <= n; u ++)//计算每一个点的出度
	{
		for(auto v : e[u])
		{
			if(bel[u] != bel[v]) outd[bel[u]] ++;//出度加1
		}
	}
	int cnts = 0, cntv = 0;
	for(int i = 1; i <= cnt; i ++)
	{
		if(outd[i] == 0)//如果第i个强连通分量出度 == 0
		{
			cnts ++;
			cntv += sz[i];//则加上第i个强连通分量的点的个数
		}
	}
	if(cnts >= 2)//则不满足题意
	{
		puts("0");
	}
	else cout << cntv << endl;//满足条件的牛的个数
}