并查集算法 详解
并查集的思想
并查集是一种树形的数据结构，用于处理不相交集的合并查询，一般具有两个基本的操作，查找确定元素在哪一个子集，合并将两个子集进行合并。
并查集的两个优化是路径压缩和启发式的合并。
金典应用是最小生成树和最大公共祖先，检测图是否有环。
并查集的构建
/*
并查集是一个数组，每一个值保存一个父节点，形成一个集合，
集合需要关注两个操作，查找父节点，合并
*/
public int find(int[] parents, int d){
int f_root = d;
while (parents[f_root] != -1){
d = parents[f_root];
}
return f_root;
}
// 合并集合，合并集合最简单的操作是将其父节点进行关联
public int union(int[] parents, int x , int y){
int x_root = find(parents,x);
int y_root = find(parents,y);
if(x_root == y_root){
return 0;
}
parents[x_root] = y_root;
return 1;
}
第二种方式作为内部类进行使用
static class DUS{
int[] parent;
public DUS(int n){
parent = new int[n];
for(int i=0;i<n;i++){
parent[i] = i;
}
}
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root){
return 0;
}
if (x_root < y_root){
parent[y_root] = x_root;
}else {
parent[x_root] = y_root;
}
return 1;
}
}
// 三种启发式合并，避免形成的树过深
class DSU {
int[] parent;
int[] rank;
int N = 6;
public DSU() {
parent = new int[N];
rank = new int[N];
for(int i=0;i<N;i++){
parent[i] = i;
}
}
// 这里顺便做路径压缩，将查到的父节点赋值给当前节点
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if(x_root == y_root){
return 0;
}
// 将大指向小进行统一
// 使用启发式合并，避免形成的树过深
if(rank[x_root] < rank[y_root]){
parent[x_root] = y_root;
}else if (rank[x_root] > rank[y_root]){
parent[y_root] = x_root;
}else{
rank[x_root]++;
parent[y_root] = x_root;
}
return 1;
}
}
eg 题目
判断图是否有环
思路是，选择边，如果当前的边的点存在集合有加入对应集合，否则开辟新集合，如果存在两个集合有的将两个集合进行合并，如果加入的点都在一个集合里，说明存在环。
1559. 二维网格图中探测环
给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。
同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。
输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
class Solution {
static class DUS{
int[] parent;
public DUS(int n){
parent = new int[n];
for(int i=0;i<n;i++){
parent[i] = -1;
}
}
public int find(int x){
while(parent[x] != -1){
x = parent[x];
}
return x;
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root){
return 0;
}
if (x_root < y_root){
parent[y_root] = x_root;
}else {
parent[x_root] = y_root;
}
return 1;
}
}
// 思路将二维数组当做一维数组，做并查集，判断存在环,将一个边的两个点加入并查集
// 将一个边的两个点加入并查集
public boolean containsCycle(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
DUS dus = new DUS(m*n);
for(int i=0;i<m;i++){
for(int j=1;j<n;j++){
if(grid[i][j-1] == grid[i][j]){
int u = dus.union(i * n + j, i * n + j - 1);
if (u == 0){
return true;
}
}
}
}
for(int i=0;i<n;i++){
for(int j=1;j<m;j++){
if(grid[j-1][i] == grid[j][i]){
int u = dus.union((j-1) * n + i, j * n + i);
if (u == 0){
return true;
}
}
}
}
return false;
}
}
684. 冗余连接
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
class DUS {
int[] parent;
public DUS (int n){
parent = new int[n+1];
for (int i=1;i<=n;i++){
parent[i] = i;
}
}
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root){
return 0;
}
if (x_root < y_root){
parent[y_root] = x_root;
}else {
parent[x_root] = y_root;
}
return 1;
}
}
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
DUS dus = new DUS(n);
for (int[] nums: edges){
int i = dus.union(nums[0],nums[1]);
if (i == 0){
return nums;
}
}
return new int[0];
}
统计图形成联通集的个数
思路在向并查集中添加完所有的边对应的点后，统计现在是顶点的个数，一个顶点是一个联通图，parent[i] = i
包括统计每一个联通图里面节点的个数
547 朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1：
输入：
[[1,1,0],
[1,1,0],
[0,0,1]]
输出：2
解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回 2 。
class Solution {
// 思路形成并查集，并将其所有节点都标记为父节点，统计父节点的个数
// 初始让所有节点父节点是本身
class DUS{
int[] parent;
public DUS(int n){
parent = new int[n];
for(int i=0;i<n;i++){
parent[i] = i;
}
}
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if(x_root == y_root){
return 0;
}
if(x_root < y_root){
parent[y_root] = x_root;
}else{
parent[x_root] = y_root;
}
return 1;
}
public int getRootNum(){
int count = 0;
for(int i=0;i<parent.length;i++){
if(parent[i] == i){
count++;
}
}
return count;
}
}
public int findCircleNum(int[][] M) {
int n = M.length;
DUS dus = new DUS(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(M[i][j] == 1 && i != j){
dus.union(i,j);
}
}
}
return dus.getRootNum();
}
}
959. 由斜杠划分的区域
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\" 表示。）。
返回区域的数目。
public int regionsBySlashes(String[] grid) {
int N = grid.length;
DSU dsu = new DSU(4 * N * N);
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c) {
int root = 4 * (r * N + c);
char val = grid[r].charAt(c);
if (val != '\\') {
dsu.union(root + 0, root + 1);
dsu.union(root + 2, root + 3);
}
if (val != '/') {
dsu.union(root + 0, root + 2);
dsu.union(root + 1, root + 3);
}
// north south
if (r + 1 < N)
dsu.union(root + 3, (root + 4 * N) + 0);
if (r - 1 >= 0)
dsu.union(root + 0, (root - 4 * N) + 3);
// east west
if (c + 1 < N)
dsu.union(root + 2, (root + 4) + 1);
if (c - 1 >= 0)
dsu.union(root + 1, (root - 4) + 2);
}
int ans = 0;
for (int x = 0; x < 4 * N * N; ++x) {
if (dsu.find(x) == x)
ans++;
}
return ans;
}
}
class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
17.07 婴儿名字
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
在结果列表中，选择字典序最小的名字作为真实名字。
示例：
输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]
static class DUS {
int[] parent;
public DUS (int n){
parent = new int[n];
for (int i=0;i<n;i++){
parent[i] = i;
}
}
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root){
return 0;
}
if (x_root < y_root){
parent[y_root] = x_root;
}else {
parent[x_root] = y_root;
}
return 1;
}
}
// 将孩子的名字编号，并将其次数统计出来
public static String[] trulyMostPopular(String[] names, String[] synonyms) {
List<String> nameList = new ArrayList<String>();
HashMap<String,Integer> map = new HashMap<String, Integer>();
for(String item: names){
int idx = item.indexOf("(");
String sub = item.substring(idx+1,item.length()-1);
String name = item.substring(0,idx);
nameList.add(name);
map.put(name,Integer.parseInt(sub));
}
Collections.sort(nameList);
DUS dus = new DUS(nameList.size());
for (String pair: synonyms){
String[] pairs = pair.substring(1,pair.length()-1).split(",");
int x = nameList.indexOf(pairs[0]);
int y = nameList.indexOf(pairs[1]);
if (x== -1 || y == -1) continue;
dus.union(x, y);
}
HashMap<String, Integer> res = new HashMap<String, Integer>();
for (int i=0;i<nameList.size();i++){
int root = dus.find(i);
String originName = nameList.get(i);
String rootName = nameList.get(root);
res.put(rootName, res.getOrDefault(rootName,0) + map.get(originName));
}
List<Map.Entry<String,Integer>> list = new ArrayList<>(res.entrySet());
String[] result = new String[res.size()];
int idx = 0;
for (Map.Entry<String,Integer> entry: list){
result[idx++] = entry.getKey() + "(" + entry.getValue() + ")";
}
return result;
}
判断两个点是不是同一个联通集里面的
判断两个点是不是同一个联通集里面的，先将形成联通集的加入形成最终的联通集，最后将判断节点依次判断父节点是否相同
990. 等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
示例 1：
输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
// 使用并查集，将小的作为父节点，
class BUS {
int[] parent;
int N = 26;
public BUS(){
parent = new int[N];
for(int i=0;i<N;i++){
parent[i] = i;
}
}
public int find(int x){
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if(x_root == y_root){
return 0;
}
if(x_root < y_root){
parent[y_root] = x_root;
}else{
parent[x_root] = y_root;
}
return 1;
}
}
public boolean equationsPossible(String[] equations) {
BUS bus = new BUS();
for(String item : equations){
int x = item.charAt(0) - 'a';
int y = item.charAt(3) - 'a';
char c = item.charAt(1);
if(c == '='){
bus.union(x,y);
}
}
for(String item : equations){
int x = item.charAt(0) - 'a';
int y = item.charAt(3) - 'a';
char c = item.charAt(1);
if(c == '!'){
int x_root = bus.find(x);
int y_root = bus.find(y);
if(x_root == y_root){
return false;
}
}
}
return true;
}
