前言
两种图中找环的方法暂且记忆这几种：
无向图：并查集、DFS
有向图：拓扑排序、DFS
无向图
参考例题：找环个数
1. 并查集
通过判断当前要连的边 u , v之间是否已经处在一个集合中，来统计环的个数。
int n, m; int fa[N]; int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) fa[i] = i; int res = 0; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; int fx = find(a), fy = find(b); if (fx != fy) fa[fx] = fy; else res++; } cout << res << endl; }
2. DFS
对于一个环 1-2-3-1 来说，从1开始dfs到2到3到1，发现1已经走过了，计数++。回溯到1，继续dfs到3，发现3也是之前走过的环中的点，计数++。所以最后答案是计数的一半。
简而言之：环始点左右都计数了，但应只取一次。
另一种方法：统计每块联通区域中的点数 V 和边数 E。E >= V 则存在环。
结论：E + P > V 就表示原图有环，否则无环。P(连通分量个数)。
int n, m; vector<int> e[N]; bool st[N]; int res = 0; void dfs(int u, int f) { st[u] = true; for (auto j: e[u]) { if (j == f) continue; if (st[j]) { res ++; continue; } dfs(j, u); } return ; } void solve() { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; e[a].pb(b); e[b].pb(a); } memset(st, 0, sizeof st); for (int i = 1; i <= n; i++) { if (!st[i]) dfs(i, -1); } cout << res / 2 << endl; }
有向图
参考例题：拓扑排序判环
1. 拓扑排序
记录每个点的入度，入度为 0 00 就加如队列继续bfs。最后判断是否还存在点入度大于 0 00 的，是则存在环。
class Solution { public: bool canFinish(int n, vector<vector<int>>& edge) { vector<int> e[n + 1]; vector<int> d(n + 1, 0); for (auto c: edge) { int a = c[0], b = c[1]; // b -> a e[b].push_back(a); d[a]++; } queue<int> q; for (int i = 0; i < n; i++) if (d[i] == 0) q.push(i); while (q.size()) { auto c = q.front(); q.pop(); for (auto j: e[c]) { if (--d[j] == 0) q.push(j); } } for (int i = 0; i < n; i++) if (d[i] > 0) return false; return true; } };
2. DFS
给状态数组 s t stst 表明含义，如代码注释所示。
class Solution { public: bool canFinish(int n, vector<vector<int>>& edge) { vector<int> e[n + 1]; for (auto c: edge) { int a = c[0], b = c[1]; // b -> a e[b].push_back(a); } int st[n + 1]; memset(st, 0, sizeof st); bool ok = true; // 无环 auto dfs = [&](auto &&dfs, int u) -> void { st[u] = 1; for (auto j: e[u]) { if (st[j] == 0) { // 未走过 dfs(dfs, j); if (!ok) return; } else if (st[j] == 1) { // 自己走过 ok = false; return ; } } st[u] = 2; // 不在探索 }; for (int i = 0; i < n && ok; i++) if (!st[i]) dfs(dfs, i); return ok; } };
