有向图、无向图找环_有向图找环

前言

两种图中找环的方法暂且记忆这几种：

• 无向图：并查集、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

有向图

参考例题：拓扑排序判环

1. 拓扑排序

记录每个点的入度，入度为 $0$ 就加如队列继续bfs。最后判断是否还存在点入度大于 $0$ 的，是则存在环。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. DFS

给状态数组 $st$ 表明含义，如代码注释所示。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27