【题目来源】 https://www.luogu.com.cn/problem/B3609 【题目描述】 给定一张 n 个点 m 条边的有向图，求出其所有的强连通分量。 注意，本题可能存在重边和自环。 【输入格式】 第一行两个正整数 n，m，表示图的点数和边数。 接下来 m 行，每行两个正整数 u 和 v 表示一条边。 【输出格式】 第一行一个整数表示这张图的强连通分量数目。 接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。 【输入样例】 6 8 1 2 1 5 2 6 5 6 6 1 5 3 6 4 3 4 【输出样例】 3 1 2 5 6 3 4 【数据范围】 对于所有数据，1≤n≤10000，1≤m≤100000。 【算法分析】 Kosaraju 算法是一种用于查找有向图中强连通分量（Strongly Connected Components, SCC）的经典算法。它的核心思想是通过两次深度优先搜索（DFS）来实现，时间复杂度为 O(V+E)，其中 V 是顶点数，E 是边数。 Kosaraju 算法模板题代码详见：https://blog.csdn.net/hnjzsyjyj/article/details/164698263 ● 算法步骤 （一）第一次 DFS（正向图） 对原始有向图进行 DFS 遍历，记录每个顶点的完成时间（即退出递归的顺序）。 将顶点按完成时间的逆序压入一个栈中（完成时间越晚的顶点越早入栈）。 （二）转置图 构建原图的转置图（将所有边的方向反转）。 （三）第二次 DFS（反向图） 从栈顶依次弹出顶点，对转置图进行 DFS。 每次 DFS 访问到的所有顶点构成一个强连通分量。 ● 为什么有效？ 第一次 DFS 确定了顶点的拓扑顺序（基于完成时间）。 转置图将原图中的强连通分量内部的环保持不变，但改变了不同分量之间的连接方向。 第二次 DFS 在转置图上按逆序访问，可以确保每次只探索同一个强连通分量内的顶点，不会跨到其他分量。 【算法代码】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> G[N],G2[N];
vector<int> group[N];
int st[N];
int post[N],post_cnt;
int scc[N],scc_cnt;
void dfs1(int u) {
st[u]=1;
for(int v:G[u]) {
if(!st[v]) dfs1(v);
}
post[++post_cnt]=u;
}
void dfs2(int u) {
st[u]=1;
scc[u]=scc_cnt;
group[scc_cnt].push_back(u);
for(int v:G2[u]) {
if(!st[v]) dfs2(v);
}
}
void kosaraju(int n) {
memset(st,0,sizeof st);
post_cnt=0;
for(int i=1; i<=n; i++) {
if(!st[i]) dfs1(i);
}
memset(st,0,sizeof st);
scc_cnt=0;
for(int i=post_cnt; i>=1; i–) {
int u=post[i];
if(!st[u]) {
++scc_cnt;
dfs2(u);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++) {
int x,y;
cin>>x>>y;
G[x].push_back(y);
G2[y].push_back(x);
}
kosaraju(n);
vector<vector<int>> all_scc;
for(int id=1; id<=scc_cnt; id++) {
sort(group[id].begin(), group[id].end());
all_scc.push_back(group[id]);
}
int total=all_scc.size();
for(int i=0; i<total; i++) {
for(int j=i+1; j<total; j++) {
int a=all_scc[i][0];
int b=all_scc[j][0];
if(a>b) swap(all_scc[i],all_scc[j]);
}
}
cout<<all_scc.size()<<"\\n";
for(int i=0; i<all_scc.size(); i++) {
for(int j=0; j<all_scc[i].size(); j++) {
cout<<all_scc[i][j]<<" ";
}
cout<<"\\n";
}
return 0;
}
/*
in:
6 8
1 2
1 5
2 6
5 6
6 1
5 3
6 4
3 4
out:
3
1 2 5 6
3
4
*/
【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/164698263 https://blog.csdn.net/hnjzsyjyj/article/details/164631569
