强连通分量随记随忘

vis用于判断某个点是否在栈中

tot表示强连通分量的数量

belong[x]表示点x所属的强连通分量

all[]与tot变量相关，表示此强连通分量的点的数量

outd[]与tot变量相关，表示此强连通分量的出度

模板代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,timestamp;
vector<int> vec[N];
int dfn[N],low[N];
stack<int> stk;
bool vis[N];
int tot;
int belong[N];
int all[N];
int outd[N];
void tarjan(int x){
	timestamp++;
	dfn[x]=timestamp;
	low[x]=timestamp;
	stk.push(x);
	vis[x]=true;
	for (int i=0;i<vec[x].size();i++)
	{
		int v=vec[x][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if (vis[v]) low[x]=min(low[x],low[v]);
	}
	if (low[x]==dfn[x])
	{
		tot++;
		while (!stk.empty())
		{
			int t=stk.top();
			stk.pop();
			vis[t]=false;
			belong[t]=tot;
			all[tot]++; 
			if (t==x) break;
		}
	}
}

int main()
{
	int x,y;
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>x>>y;
		vec[x].push_back(y);
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i);
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<vec[i].size();j++)
		{
			int v=vec[i][j];
			if (belong[i]!=belong[v]) outd[belong[i]]++;
		}
	}
	int cnt=0,loc;
	for (int i=1;i<=tot;i++)
		if (outd[i]==0)
		{
			cnt++;
			loc=i;
		}
	if (cnt==1) cout<<all[loc];
	else cout<<0;
	return 0;
}