【题目来源】https://www.luogu.com.cn/problem/B3609【题目描述】给定一张 n 个点 m 条边的有向图求出其所有的强连通分量。注意本题可能存在重边和自环。【输入格式】第一行两个正整数 nm表示图的点数和边数。接下来 m 行每行两个正整数 u 和 v 表示一条边。【输出格式】第一行一个整数表示这张图的强连通分量数目。接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量第二行输出 2 号点所在强连通分量若已被输出则改为输出 3 号点所在强连通分量以此类推。每个强连通分量按节点编号大小输出。【输入样例】6 81 21 52 65 66 15 36 43 4【输出样例】31 2 5 634【数据范围】对于所有数据1≤n≤100001≤m≤100000。【算法分析】Kosaraju 算法是一种用于查找有向图中强连通分量Strongly Connected Components, SCC的经典算法。它的核心思想是通过两次深度优先搜索DFS来实现时间复杂度为 O(VE)其中 V 是顶点数E 是边数。Kosaraju 算法模板题代码详见https://blog.csdn.net/hnjzsyjyj/article/details/164698263● 算法步骤一第一次 DFS正向图对原始有向图进行 DFS 遍历记录每个顶点的完成时间即退出递归的顺序。将顶点按完成时间的逆序压入一个栈中完成时间越晚的顶点越早入栈。二转置图构建原图的转置图将所有边的方向反转。三第二次 DFS反向图从栈顶依次弹出顶点对转置图进行 DFS。每次 DFS 访问到的所有顶点构成一个强连通分量。● 为什么有效第一次 DFS 确定了顶点的拓扑顺序基于完成时间。转置图将原图中的强连通分量内部的环保持不变但改变了不同分量之间的连接方向。第二次 DFS 在转置图上按逆序访问可以确保每次只探索同一个强连通分量内的顶点不会跨到其他分量。【算法代码】#includebits/stdc.h using namespace std; const int N1e55; vectorint G[N],G2[N]; vectorint 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_cnt0; for(int i1; in; i) { if(!st[i]) dfs1(i); } memset(st,0,sizeof st); scc_cnt0; for(int ipost_cnt; i1; i--) { int upost[i]; if(!st[u]) { scc_cnt; dfs2(u); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cinnm; for(int i1; im; i) { int x,y; cinxy; G[x].push_back(y); G2[y].push_back(x); } kosaraju(n); vectorvectorint all_scc; for(int id1; idscc_cnt; id) { sort(group[id].begin(), group[id].end()); all_scc.push_back(group[id]); } int totalall_scc.size(); for(int i0; itotal; i) { for(int ji1; jtotal; j) { int aall_scc[i][0]; int ball_scc[j][0]; if(ab) swap(all_scc[i],all_scc[j]); } } coutall_scc.size()\n; for(int i0; iall_scc.size(); i) { for(int j0; jall_scc[i].size(); j) { coutall_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/164698263https://blog.csdn.net/hnjzsyjyj/article/details/164631569