$Tarjan$

#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 5;
int vis[N], st[N];//st模拟栈，vis记录是否入栈 
int scc[N], sz[N], sc;//sc记录所在SCC的编号，scc记录在第几个SCC，sz记录大小 
int dfn[N], low[N];//dfn记录遍历次序，low记录祖先 
vector<int> g[N];
int n, m, dfncnt, top;
inline void tarjan(int u)
{
	dfn[u] = low[u] = ++dfncnt;
	st[++top] = u;//入栈
	vis[u] = 1;
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(!dfn[v]){//如果没被访问 
			tarjan(v);//继续往下搜索 
			low[u] = min(low[u], low[v]);
		}
		else if(vis[v]){
			low[u] = min(low[u], dfn[v]);
		}
	} 
	if(dfn[u] == low[u]){
		sc++;//记录编号 
		while(st[top] != u){//栈顶不等于u 
			scc[st[top]] = sc;//记录SCC 
			sz[sc]++;//第sc个SCC大小++ 
			vis[st[top]] = 0;//出栈 
			top--;//出栈	
		}
		//将u记录到SCC中 
		scc[st[top]] = sc; 
		sz[sc]++;
		vis[st[top]] = 0;
		top--;
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);//有向图 
	}
	for(int i = 1; i <= n; i++){
		if(!dfn[i]) tarjan(i);//输出 
	}
	return 0;
}

缩点

#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 5;
int vis[N], st[N];//st模拟栈，vis记录是否入栈 
int scc[N], sz[N], sc;//sc记录所在SCC的编号，scc记录在第几个SCC，sz记录大小 
int dfn[N], low[N];//dfn记录遍历次序，low记录祖先 
vector<int> g[N], G[N];
int n, m, dfncnt, top;
inline void tarjan(int u)
{
	dfn[u] = low[u] = ++dfncnt;
	st[++top] = u;//入栈
	vis[u] = 1;
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(!dfn[v]){//如果没被访问 
			tarjan(v);//继续往下搜索 
			low[u] = min(low[u], low[v]);
		}
		else if(vis[v]){
			low[u] = min(low[u], dfn[v]);
		}
	} 
	if(dfn[u] == low[u]){
		sc++;//记录编号 
		while(st[top] != u){//栈顶不等于u 
			scc[st[top]] = sc;//记录SCC 
			sz[sc]++;//第sc个SCC大小++ 
			vis[st[top]] = 0;//出栈 
			top--;//出栈	
		}
		//将u记录到SCC中 
		scc[st[top]] = sc; 
		sz[sc]++;
		vis[st[top]] = 0;
		top--;
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);//有向图 
	}
	for(int i = 1; i <= n; i++){
		if(!dfn[i]) tarjan(i);//输出 
	}
	//缩点，构建DAG图 
	for(int u = 1; u <= n; u++){
		for(int i = 0; i < g[u].size(); i++){
			int v = g[u][i];
			if(scc[u] != scc[v]) G[scc[u]].push_back(scc[v]);
		}
	}
	return 0;
}