摘要: 无向图上的环的判定
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】 我的网站:潮汐朝夕的生活实验室 我的公众号:算法题刷刷 我的知乎:潮汐朝夕 我的github:FennelDumplings 我的leetcode:FennelDumplings
本文我们系统梳理一下判定无向图中是否存在环的问题。首先介绍四种算法,分别为 BFS、DFS、并查集、拓扑排序,均为图上的主流算法,建议全都掌握。
然后我们看两个相关的问题,一个是给定一条边判断该边是否在环上,另一个是判定是否存在边数至少为 4 的环。
$1 判定:是否存在环(模板) 无向图中环判定:在 DFS 的过程中找到一个点,它不是 prev 点(DFS前驱)而又在此前遍历过,则形成环。
但注意如果是有向图,则访问到一个以前访问过的点并不代表形成环。参考 有向图的环 。
1 bool has_cycle (const vector <vector <int >>& g) ;
算法1: dfs 染色 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 bool dfs (const vector <vector <int >>& g, int u, int prev, vector <bool >& visited) { for (int v: g[u]) { if (v == prev) continue ; if (visited[v]) return true ; visited[v] = true ; if (dfs(g, v, u, visited)) return true ; } return false ; } bool has_cycle (const vector <vector <int >>& g) { int n = g.size(); vector <bool > visited (n, false ) ; for (int i = 0 ; i < n; ++i) { if (visited[i]) continue ; visited[i] = true ; if (dfs(g, i, -1 , visited)) return true ; } return false ; }
算法2: bfs 染色 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 29 30 31 32 33 34 35 36 37 38 39 40 41 struct State { int node; int prev; State(int node, int prev):node(node),prev(prev){} }; bool bfs (const vector <vector <int >>& g, vector <bool >& visited, int start) { queue <State> q; q.push(State(start, -1 )); while (!q.empty()) { State s = q.front(); for (int son: g[s.node]) { if (son == s.prev) continue ; if (visited[son]) return true ; visited[son] = true ; q.push(State(son, s.node)); } } return false ; } bool has_cycle (const vector <vector <int >>& g) { int n = g.size(); vector <bool > visited (n, false ) ; for (int i = 0 ; i < n; ++i) { if (visited[i]) continue ; visited[i] = true ; if (bfs(g, visited, i)) return true ; } return false ; }
算法3: 并查集 Kruskal 算法中的一步。
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class UnionFindSet { public : UnionFindSet(int N) { _father = vector <int >(N + 1 , -1 ); _rank = vector <int >(N + 1 , 1 ); for (int i = 0 ; i <= N; ++i) _father[i] = i; } bool same (int x, int y) { return _find(x) == _find(y); } void merge (int x, int y) { x = _find(x); y = _find(y); if (x == y) return ; if (_rank[x] < _rank[y]) _father[x] = y; else _father[y] = x; if (_rank[x] == _rank[y]) ++_rank[x]; } private : vector <int > _father; vector <int > _rank; int _find(int x) { if (_father[x] == x) return x; return _father[x] = _find(_father[x]); } }; bool has_cycle (const vector <vector <int >>& g) { int n = g.size(); UnionFindSet unifindset (n) ; for (int u = 0 ; u < n; ++u) { for (int v: g[u]) { if (unifindset.same(u, v)) return true ; unifindset.merge(u, v); } } return false ; }
算法4: 拓扑排序 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 29 30 31 32 33 34 35 36 37 38 bool has_cycle (const vector <vector <int >>& g) { int n = g.size(); vector <int > degrees (n) ; for (int u = 0 ; u < n; ++u) degrees[u] = g[u].size(); queue <int > q; vector <bool > visited (n, false ) ; for (int u = 0 ; u < n; ++u) if (degrees[u] == 1 ) { q.push(u); visited[u] = true ; } while (!q.empty()) { int u = q.front(); q.pop(); for (int v: g[u]) { if (visited[v]) continue ; --degrees[v]; if (degrees[v] == 1 ) { visited[v] = true ; q.push(v); } } } for (int u = 0 ; u < n; ++u) if (degrees[u] > 1 ) return true ; return false ; }
$2 判定:边是否在环上 树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。
提示:
1 2 3 4 5 6 7 n == edges.length 3 <= n <= 1000 edges[i].length == 2 1 <= ai < bi <= edges.length ai != bi edges 中无重复元素 给定的图是连通的
示例 1: 输入: edges = [[1,2], [1,3], [2,3]] 输出: [2,3]
示例 2: 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]
算法1:并查集 依次枚举边表中的边 u v ,过程中维护并查集,若并查集中 u , v 属于同一个集合,则此前枚举过的边已经构成了 u , v 之间的一条路径,此时再连接边 u , v ,则构成一个环,u v 就是环上的边。
由于图的形态是树加上一条边,因此只有一个环,又因为枚举顺序是从左到右,于是 u v 是环上的边在 edges 中最后出现的。
代码 (C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : vector <int > findRedundantConnection (vector <vector <int >>& edges) { int N = edges.size(); UnionFindSet unionfindset (N) ; for (vector <int > &edge: edges) { int x = edge[0 ], y = edge[1 ]; if (unionfindset.same(x, y)) return vector <int >({x, y}); else unionfindset.merge(x, y); } return vector <int >(); } };
算法2:拓扑排序 拓扑排序之后,degrees 中的所有度大于 1 的节点的任意组合都是可删的边。
代码 (C++) 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 void topsort (const vector <vector <int >>& g, vector <int >& degrees) { int n = g.size(); for (int u = 0 ; u < n; ++u) degrees[u] = g[u].size(); queue <int > q; vector <bool > visited (n, false ) ; for (int u = 0 ; u < n; ++u) if (degrees[u] == 1 ) { q.push(u); visited[u] = true ; } while (!q.empty()) { int u = q.front(); q.pop(); for (int v: g[u]) { if (visited[v]) continue ; --degrees[v]; if (degrees[v] == 1 ) { visited[v] = true ; q.push(v); } } } } class Solution {public : vector <int > findRedundantConnection (vector <vector <int >>& edges) { int N = edges.size(); vector <vector <int >> g (N + 1 ) ; for (const vector <int > &edge: edges) { g[edge[0 ]].push_back(edge[1 ]); g[edge[1 ]].push_back(edge[0 ]); } vector <int > degrees (N + 1 , 0 ) ; topsort(g, degrees); for (int i = N - 1 ; i >= 0 ; --i) if (degrees[edges[i][0 ]] > 1 && degrees[edges[i][1 ]] > 1 ) return edges[i]; return {}; } };
在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。
输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。
返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
提示:
1 2 3 4 n == edges.length 3 <= n <= 1000 edges[i].length == 2 1 <= ui, vi <= n
示例 1: 输入:edges = [[1,2],[1,3],[2,3]] 输出:[2,3]
示例 2: 输入:edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] 输出:[4,1]
算法:并查集 上一题是一棵无根树(连通无环无向图)加了一条边形成一个环,删去一条环上的边。
本题是一棵有根树(有向图,有一个根节点,其余所有点均为根的后继,除根外每个节点有且只有一个父节点)。在有根树的基础上加了一条边,我们要删除一条边,使得剩余部分形成有根树。
在有根树上新增一条边,可能会有两种情况:
一种情况是新增的边以根为终点,由于根的入度为 0,加边后所有顶点的入度均为 1,也就是对任意节点 u ,其父节点 f a [ u ] 存在且唯一,上图左边画的就是这种情况。此时可以将所有边视为无向边,图视为无向图,然后删掉该无向图的环上的任意一条边即可,算法与前面的 684 题一样。
另一种情况是新增的边以除根以外的另一个顶点为终点,这样该顶点的入度就会变为 2,即有两条入边。那么应该删掉的边就只能是这两条之一。上图右边画的就是这种情况。不论删掉哪一条,都会变成除了一个顶点入度为0,其余顶点入度均为1的情况,但是图可能不连通,例如上图右边被黑色圈出的两条边,如果删掉蓝色那一条,就会造成图不连通的情况。
因此我们可以直接删除一条边,然后看剩余部分视为无向图,判断其是否连通,若连通,则被删的边是答案;若不连通,则另一条边是答案。
代码 (C++) 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 class UnionFindSet { public : UnionFindSet(int N) { _father = vector <int >(N + 1 , -1 ); _rank = vector <int >(N + 1 , 1 ); for (int i = 0 ; i <= N; ++i) _father[i] = i; } bool same (int x, int y) { return _find(x) == _find(y); } void merge (int x, int y) { x = _find(x); y = _find(y); if (x == y) return ; if (_rank[x] < _rank[y]) _father[x] = y; else _father[y] = x; if (_rank[x] == _rank[y]) ++_rank[x]; } private : vector <int > _father; vector <int > _rank; int _find(int x) { if (_father[x] == x) return x; return _father[x] = _find(_father[x]); } }; class Solution {public : vector <int > findRedundantDirectedConnection (vector <vector <int >>& edges) { int N = edges.size(); vector <int > fa (N + 1 , -1 ) ; vector <int > tmp1 (2 , -1 ) ; vector <int > tmp2 (2 , -1 ) ; for (const vector <int > &edge: edges) { if (fa[edge[1 ]] != -1 ) { tmp1 = edge; tmp2[0 ] = fa[edge[1 ]]; tmp2[1 ] = edge[1 ]; break ; } fa[edge[1 ]] = edge[0 ]; } if (tmp1[0 ] == -1 ) { UnionFindSet unionfindset (N) ; for (const vector <int > &edge: edges) { int x = edge[0 ], y = edge[1 ]; if (unionfindset.same(x, y)) return edge; unionfindset.merge(x, y); } return vector <int >(2 , -1 ); } UnionFindSet unionfindset (N) ; for (const vector <int > &edge: edges) { if (edge == tmp1) continue ; int x = edge[0 ], y = edge[1 ]; if (unionfindset.same(x, y)) return tmp2; unionfindset.merge(x, y); } return tmp1; } };
$3 判定:是否存在边数至少为4的环
给你一个二维字符网格数组 grid ,大小为 m x n ,你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子,你可以移动到它上、下、左、右四个方向相邻的格子之一,可以移动的前提是这两个格子有 相同的值 。
同时,你也不能回到上一次移动时所在的格子。比方说,环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的,因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环,请你返回 true ,否则返回 false 。
提示:
1 2 3 4 5 m == grid.length n == grid[i].length 1 <= m <= 500 1 <= n <= 500 grid 只包含小写英文字母。
示例 1:
输入:grid = [[“a”,”a”,”a”,”a”],[“a”,”b”,”b”,”a”],[“a”,”b”,”b”,”a”],[“a”,”a”,”a”,”a”]] 输出:true 解释:如下图所示,有 2 个用不同颜色标出来的环:
示例 2:
输入:grid = [[“c”,”c”,”c”,”a”],[“c”,”d”,”c”,”c”],[“c”,”c”,”e”,”c”],[“f”,”c”,”c”,”c”]] 输出:true 解释:如下图所示,只有高亮所示的一个合法环:
示例 3: 输入:grid = [[“a”,”b”,”b”],[“b”,”z”,”b”],[“b”,”b”,”a”]] 输出:false
算法:DFS 我们要判断无向无权图上是否存在长度大于等于 4 的环。
在无向图上判定环的 DFS 算法的基础上,维护额外信息: d[u] := u 到源点 start 的距离
,在判定到环上的边时候,多一步距离的判断:边上的两点到源的距离:
1 2 3 4 5 6 7 if (visited[x][y]){ if (dist[i][j] - dist[x][y] + 1 >= 4 ) return true ; continue ; }
代码 (C++) 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution {public : bool containsCycle (vector <vector <char >>& grid) { int n = grid.size(), m = grid[0 ].size(); vector <vector <bool >> visited (n, vector <bool >(m, false )) ; vector <vector <int >> dist (n, vector <int >(m, 0 )) ; for (int i = 0 ; i < n; ++i) for (int j = 0 ; j < m; ++j) { if (visited[i][j]) continue ; visited[i][j] = true ; dist[i][j] = 1 ; if (dfs(grid, i, j, visited, dist)) return true ; } return false ; } private : int dx[4 ] = {0 , 0 , 1 , -1 }; int dy[4 ] = {1 , -1 , 0 , 0 }; bool dfs (const vector <vector <char >>& grid, int i, int j, vector <vector <bool >>& visited, vector <vector <int >>& dist) { int n = grid.size(), m = grid[0 ].size(); for (int d = 0 ; d < 4 ; ++d) { int x = i + dx[d]; int y = j + dy[d]; if (x < 0 || x >= n || y < 0 || y >= m) continue ; if (grid[x][y] != grid[i][j]) continue ; if (visited[x][y]) { if (dist[i][j] - dist[x][y] + 1 >= 4 ) return true ; continue ; } visited[x][y] = true ; dist[x][y] = dist[i][j] + 1 ; if (dfs(grid, x, y, visited, dist)) return true ; } return false ; } };