并查集

并查集解决的问题

连通问题 寻找路径

并查集的数据结构

两个数组：size[n]，parent[n]分别存储连通分量大小以及节点的父节点

并查集的操作

Find操作 寻找连通分量的根

1
2
3
4
5
int Find(int node){
	int root = node;
	while(parent[root]!=root) //只要父节点不是本身 就一直向上找
		return root;
}

Union操作 将连通分量合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Union(int p,int q){
	int root1 = Find(p);
	int root2 = Find(q);
	
	if(root1 == root2) 
		return; //已经在一个连通分量 不操作
	if(size[root1] >= size[root2]){ //把小的分量接到大的分量上
		parent[root2] = root1;
		size[root1] += size[root2];
	}
	else{
		parent[root1] = root2;
		size[root2] += size[root1];
	}
}

力扣684 冗余连接

题目分析：树是连通的 但是没有环 树多加一条边就会构成环 当添加一条边时发现这条边两端对应的分量已经连通 说明重复添加了 所以只需要初始化一个并查集 遍历给的边 依次对两端Find检测是否连通，如果已经连通就说明当前的边是冗余的边并返回，如果不冗余就进行Union操作

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
class Solution {
public:
    bool Find(vector<int> &nodes,int node){
    	int root = node;
		while(nodes[root]!=root) //只要父节点不是本身 就一直向上找
			return root;
    };

    void Union(vector<int> &nodes,vector<int> &sizes,int node1,int node2){
        int root1 = root(nodes,node1);
        int root2 = root(nodes,node2);
        if(root1==root2)
            return;
        if(sizes[root1]>=sizes[root2]){
            nodes[root2] = root1;
            sizes[root1]+=sizes[root2];
        }
        else{
            nodes[root1] = root2;
            sizes[root2]+=sizes[root1];
        }
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size(); //注意树的边数量=n-1，加上一条边那就是n
        vector<int> nodes(n+1);
        vector<int> sizes(n+1);
        for(int i =1;i<=n;++i){
            sizes[i]=1;
            nodes[i] = i;
        }

        for(auto edge:edges){
            int node1 = edge[0];
            int node2 = edge[1];
            if(Find(nodes,node1,node2))
                return edge;
            Union(nodes,sizes,node1,node2);
        }
    return vector<int>{};
    }
};