正向反向分别搜索如果两次搜索经过的点都等于了总的点数则该图联通
#include<iostream> #include<algorithm> #include<vector> #include<stack> using namespace std; const int M = 10010; vector<int>raod[M];//通过vector实现邻接表存图 stack<int>s;//每访问过一个节点就存进栈里，当遇见关键点的时候依次取出使用cnt数组 int dfn[M], low[M];//来把每个结点对应的cnt数组值变成关键点对应的scnt； int dfn_cnt; int cnt[M]; int acnt; int n, m; void TarJan(int u) { dfn[u] = low[n] = dfn_cnt++; s.push(u); for (int i = 0; i < raod[u].size(); i++) { int v = raod[u][i]; if (!dfn[v]) TarJan(v), low[u] = min(low[u], low[v]); else { low[u] = min(low[u], dfn[v]); } } if (dfn[u] == low[u]) { acnt++; while (1) { int v = s.top(); s.pop(); cnt[v] = acnt++; if (u == v) break; } } } int main() { while (cin >> n >> m) { if (n == 0 && m == 0) break; for (int i = 0; i <= n; i++) { dfn[i] = low[i] = cnt[i] = 0; raod[i].clear(); } acnt = dfn_cnt = 0; while (m--) { int u, v; cin >> u >> v; raod[u].push_back(v); } for (int i = 1; i <= n; i++) { if (!cnt[i]) TarJan(i); } int i; for (i = 1; i <= n; i++) { if (cnt[i] != cnt[1]) { cout << "No\n"; break; } } if (i > n) cout << "Yes\n"; } return 0; } }用tarjan算法，求出每一个节点所对应的缩点的值， 如果缩点的个数==1，那么证明就会只有一个强连通分量！也就是强连通图 Tarjan算法是用来求强连通分量的，它是一种基于DFS（深度优先搜索）的算法，每个强连通分量为搜索树中的一棵子树。并且运用了数据结构栈。 在介绍详细原理前，先引入两个非常重要的数组：dfn[ ] 与 low[ ] dfn[ ]：就是一个时间戳（被搜到的次序），一旦某个点被DFS到后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以常根据dfn的值来判断是否需要进行进一步的深搜。 low[ ]：该子树中，且仍在栈中的最小时间戳，像是确立了一个关系，low[ ]相等的点在同一强连通分量中。 注意初始化时 dfn[ ] = low[ ] = ++cnt. (https://blog.csdn.net/qq_34374664/article/details/77488976)认真 看完这篇博客tarjan算法也算是知道一点了 直接上代码
#include<iostream> #include<algorithm> #include<vector> #include<stack> using namespace std; const int M = 10100; vector<int>raod[M];//通过vector实现邻接表存图 stack<int>s;//每访问过一个节点就存进栈里，当遇见关键点的时候依次取出使用cnt数组 int dfn[M], low[M];//来把每个结点对应的cnt数组值变成关键点对应的scnt； int dfn_cnt; int cnt[M]; int acnt; int n, m; void TarJan(int u) { dfn[u] = low[u] = dfn_cnt++; s.push(u); for (int i = 0; i < raod[u].size(); i++) { int v = raod[u][i]; if (!dfn[v]) TarJan(v), low[u] = min(low[u], low[v]); else { low[u] = min(low[u], dfn[v]); } } if (dfn[u] == low[u]) { acnt++; while (1) { int v = s.top(); s.pop(); cnt[v] = acnt; if (u == v) break; } } } int main() { while (cin >> n >> m) { if (n == 0 && m == 0) break; for (int i = 0; i <= n; i++) { dfn[i] = 0, low[i] = 0, cnt[i] = 0; raod[i].clear(); } acnt = 0; dfn_cnt = 0; while (m--) { int u, v; cin >> u >> v; raod[u].push_back(v); } for (int i = 1; i <= n; i++) { if (!cnt[i]) TarJan(i); } int i; for (i = 1; i <= n; i++) { if (cnt[i] != cnt[1]) { cout << "No\n"; break; } } if (i > n) cout << "Yes\n"; } return 0; }