图的动态连通性问题
1.当一个图已经建好的时候, 图上的连通性就被唯一的确定下来; 但我们通常要处理的是图上的连通性在动态条件下的场景, 也就是说会将图上某些部分的节点相互关联起来, 或者判断当前两个是否连通这样的问题 (判断连通性其实用 dfs 和 bfs 都可以解决)
连通是一种等价关系, 它具有自反性/对称性/传递性三种性质. 为了能够构建这种图上的动态连通性, 设计了 Union-Find 这种数据结构, 能够帮助我们快速地进行动态连通性的操作.先想下用什么结构能表示动态连通性?
想想看怎么让相互有关系的节点能被”凑到一堆”, “找到同伙”, “凑到一堆” 本质是在干一件什么事? 相当于大家认一个共同的”祖宗”, A 的祖宗是它 B 的祖宗也是它, 那么AB就是同宗同脉, 即AB就是连通的; 现在还有个新人C想问和B是不是连通的, 那么只需要找B和C有没有共同的祖宗. 因此, 我们用要构建根节点, 因此想到用树模型, 所有节点无非都是要确定, 我的祖宗和你的祖宗是不是同一个祖宗的问题. 首先我们定义什么是祖宗(也就是根节点), 最简单的定义就是对于根节点来说, 它的父指针指向它自己, 我们定义这就是根节点.
在设计这种结构上
1.想要判断两个节点是否连通, 只要判断当前节点往上追溯找到指向的根节点和另一个节点往上追溯指向的根节点是否相同.
2.想要将两个节点连通起来, 只需要让一个节点的父指针连接到另一个树节点的根节点上. 也就是 A 认 B 的祖宗为爹, 那么AB自然就是同宗同脉, 连通起来.
基础的数据结构实现如下
// 连通分量的个数
int count;
// 记录每个节点的父节点, 如果是根节点满足parent[x] == x
vector<int> parent;
// 首先设置每个节点都是根节点
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
// 寻找根节点: 基础方法, 为了方便理解, 实际使用的时候用下面的更高效的解法
int findRoot(int x) {
// 如果当前节点不是父节点
while (parent[x] != x)
// 一级一级往上寻找根节点
x = parent[x];
return x;
}
// 判断p和q是否是连通的: 只需要分别找到根节点, 然后看下根节点是不是一个.
bool ifConnected(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(p);
if (rootP == rootQ)
return true;
return false;
}
// 构建p和q之间的连通关系
void union(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(p);
if (rootP == rootQ)
return;
// 将p的根节点挂在q根节点下面: 让p的根节点的父节点指向q的根节点
parent[rootP] = rootQ;
// 反着挂也可以
// parent[rootQ] = rootP;
// 连通分量的个数减少1个
--count;
}
在找根节点的过程中可以优化, 一级一级找根节点的时候, 我们比较抵触如果是糖葫芦串一样的多代单传的这种情况, 因此引入了一种路径压缩的技巧, 将当前节点x到根节点之间所有的节点都直接接入到根节点的下面, 然后此时我们要的根节点就是当前的父节点.
int findRoot(int x) {
int root = x;
// 找到根节点
while (parent[root] != root) {
root = parent[root];
}
// 然后把[x, root)之间的所有节点都直接接入到根节点下面
int old_parent = parent[x];
while (x != root) {
// 将当前节点直接接到root上面
parent[x] = root;
// 往上追溯一个节点
x = old_parent;
old_parent = parent[old_parent];
}
return root;
}
这个可以写成递归的形式, 代码会非常简洁, 但是可能不太直观, 但只需要理解核心思想: 把[x, root) 之间的所有节点都挂在根节点上, 就能写得出如上逻辑, 注意最终我们想要的根节点此时是parent[x];
// 路径压缩, 递归写法, 实际解决问题的时候用这个方法
int findRoot(int x) {
int (parent[x] != x) {
parent[x] = findRoot(parent[x])
}
return parent[x];
}
UnionFind 和 dfs/bfs 的区别
这三类算法算法都是在解决搜索的问题, 只不过 dfs/bfs 在处理问题上有所区别
1.uf 有其独特的优势, 能够快速帮我们找到等价类
2.dfs 写起来很方便, bfs 逻辑不容易出错. 能用 dfs 还是 dfs 写起来快一些, 因为 bfs 和 uf 都要引入辅助的数据结构, 其中 uf 每次得手写时间比较长.
130.被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例 1：
输入：board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
输出：[[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。示例 2：输入：board = [[“X”]] 输出：[[“X”]]
分析:
1.dfs 解法, 对边缘开始搜索, 将能到达的区域全部替换了一个特殊字符 #, 然后将所有剩下的 O 都用 X 填充
2.uf 解法, 将所有的边缘 O 的合并成一个集合, 比如共同指向一个 dummy 根节点; 然后扫中间部分的 O 的四个方向, 如果四个方向下的邻居和当前节点都是 O, 那么让它们两个 union 一下; 最后扫描所有的非边缘节点, 如果和 dummy 没有连通那么就更改为 X
3.将二维的坐标可以映射到一维的数组里面, 映射方法为二维坐标 (x,y), 棋盘 m 行 n 列, 那么映射完的坐标为 x n + y, 因为 [0, .., m n-1]i 映射完毕之后, 可以将 m*n 这个作为 dummy 节点的值
4.写起来 uf 解法比 dfs 解法时间要长一些, 二维图上搜索可以直接判断还是直接用 dfs 方便
class Solution {
public:
int findRoot(vector<int>& parent, int x) {
// 路径压缩
if (parent[x] != x) {
parent[x] = findRoot(parent, parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q, vector<int>& parent) {
int rootP = findRoot(parent, p);
int rootQ = findRoot(parent, q);
return rootP == rootQ;
}
void unionData(int p, int q, vector<int>& parent) {
int rootP = findRoot(parent, p);
int rootQ = findRoot(parent, q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
return;
}
void solve(vector<vector<char>>& board) {
if (board.empty())
return;
int m = board.size();
int n = board[0].size();
int dummy = m * n;
vector<int> parent(m * n + 1);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
parent[i * n + j] = i * n + j;
}
}
parent[dummy] = dummy;
for (int i = 0; i < m; ++i) {
if (board[i][0] == 'O')
unionData(i * n, dummy, parent);
if (board[i][n-1] == 'O')
unionData(i * n + n - 1, dummy, parent);
}
for (int j = 0; j < n; ++j) {
if (board[0][j] == 'O')
unionData(j, dummy, parent);
if (board[m-1][j] == 'O')
unionData(n * (m-1) + j, dummy, parent);
}
vector<vector<int>> d = {{1,0}, {0,1}, {-1,0}, {0, -1}};
for (int i = 1; i < m - 1; ++i) {
for (int j = 1; j < n - 1; ++j) {
if (board[i][j] == 'O') {
for (int k = 0; k < 4; ++k) {
int x = i + d[k][0];
int y = j + d[k][1];
if (board[x][y] == 'O')
unionData(i * n + j, x * n + y, parent);
}
}
}
}
for (int i = 1; i < m - 1; ++i) {
for (int j = 1; j < n - 1; ++j) {
if (!ifConnected(dummy, i * n + j, parent)) {
board[i][j] = 'X';
}
}
}
return;
}
};
990.等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。示例 1：输入：[“a==b”,”b!=a”] 输出：false 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2：输入：[“b==a”,”a==b”] 输出：true 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：输入：[“a==b”,”b==c”,”a==c”] 输出：true
示例 4：输入：[“a==b”,”b!=c”,”c==a”] 输出：false
示例 5：输入：[“c==c”,”b==d”,”x!=z”] 输出：true
分析:
1.题目中要求我们去区分能否完成一组满足等价性的判断, 其实相当于满足一种等价关系的连接, 我们发现, ==符号具有自反/传递/对称性的性质; 因此我们处理将==的这些关系都合并连通起来
2.具体来讲, 将任意一组关系进行连通 union, 然后再判断 != 的关系里面, 有没有哪组违反了已经构建好的连通关系, 如果违反了那么就是 false
class Solution {
public:
int findRoot(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = findRoot(parent, parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q, vector<int>& parent) {
int rootP = findRoot(parent, p);
int rootQ = findRoot(parent, q);
return rootP == rootQ;
}
void unionData(int p, int q, vector<int>& parent) {
int rootP = findRoot(parent, p);
int rootQ = findRoot(parent, q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
return;
}
bool equationsPossible(vector<string>& equations) {
vector<int> parent(26);
for (int i = 0; i < 26; ++i)
parent[i] = i;
for (string s : equations) {
if (s[1] == '=') {
int x = s[0] - 'a';
int y = s[3] - 'a';
unionData(x, y, parent);
}
}
for (string s : equations) {
if (s[1] == '!') {
int x = s[0] - 'a';
int y = s[3] - 'a';
if (ifConnected(x, y, parent)) {
return false;
}
}
}
return true;
}
};
547.省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。示例 1：输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2
示例 2：输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3
分析:
1.城市相连的意思是将一些节点合并, 省份的数量其实就是相连的连通分量的个数
class Solution {
public:
int findRoot(int x, vector<int>& parent) {
if (parent[x] != x) {
parent[x] = findRoot(parent[x], parent);
}
return parent[x];
}
void unionData(int p, int q, vector<int>& parent, int& count) {
int rootP = findRoot(p, parent);
int rootQ = findRoot(q, parent);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
--count;
return;
}
int findCircleNum(vector<vector<int>>& isConnected) {
if (isConnected.empty())
return 0;
int n = isConnected.size();
int count = n;
vector<int> parent(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (isConnected[i][j] == 1) {
unionData(i, j, parent, count);
}
}
}
return count;
}
};
261.以图判树
给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。示例 1：输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] 输出: true
示例 2: 输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] 输出: false
分析:
1.判定树结构的条件: 如果图里面有环, 那么一定不能产生一棵树, 但只判断图里面是否有环还不够充分; 要用到所有的节点生成树结构, 所以要生成一颗生成树, 仍然采用并查集的方法进行逐个 union, 最终得到的连通分量的个数只能是 1; 因此采用生成并查集的方式去判定
class Solution {
private:
vector<int> parent;
int count;
public:
int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q) {
return (findRoot(p) == findRoot(q)) ? true : false;
}
void unionData(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
--count;
return;
}
bool validTree(int n, vector<vector<int>>& edges) {
parent.resize(n);
count = n;
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
for (vector<int> edge : edges) {
int p = edge[0];
int q = edge[1];
if (ifConnected(p, q)) {
return false;
}
unionData(p, q);
}
return (count == 1) ? true : false;
}
};
转载请注明来源, from goldandrabbit.github.io
