高阶数据结构学习之并查集

1并查集–思路引入

并查集是一个森林
森林：多棵树构成

1.1整体思路

特点：
1.一个位置值是负数，那他就是树的根，这个负数绝对值就是这棵树数据个数
2.一个位置值是正数，那他就是双亲的下标

当1和8进行合并时

1.2压缩路径

当findroot时，需要跳很多次时，则可以进行压缩路径

在查找根的时候，发现不是一层或少数层
就可以进行压缩

方法：
1.合并两个节点的时候，控制数据量小的合并大的
2.查找根节点的时候，将x到root路径上的所有节点的双亲改为root

2并查集代码

#pragma once
#include
using namespace std;
#include
#include
#include

//template
//class UnionFindSet
//{
//public:
//	UnionFindSet(const T*a,size_t n)
//	{
//		for (size_t i = 0; i < n; i++)
//		{
//			_a.push_back(a[i]);
//			_IndexMap[a[i]] = i;
//		}
//		
//	}
//
//private:
//	vector _a;         //编号找人
//	map _IndexMap;//人找编号
//};


//并查集
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n,-1)
	{}

	//合并
	void Union(int x1,int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 == root2) return;

		// 
		if (abs(_ufs[root1]) < abs(_ufs[root2])) 
			swap(root1, root2);

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	//寻找x的根
	int FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}

		//路径压缩
		//将root下的所有节点的双亲改为root
		while (_ufs[x] > 0)
		{
			int parents = _ufs[x];
			_ufs[x] = root;
			x = parents;
		}

		return root;
	}

	//判断是否在一个集合
	bool InSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	//有几个树
	size_t SetSize()
	{
		size_t ret = 0;
		for (int i = 0; i < _ufs.size(); i++)
			if (_ufs[i] < 0) ret++;
		return ret;
	}

private:
	vector<int> _ufs;
	

};

//测试代码
void Test()
{
	UnionFindSet ufs(10);
	ufs.Union(8, 9);
	ufs.Union(7, 8);
	ufs.Union(5, 6);
	ufs.Union(6, 7);
	ufs.Union(4, 5);
	ufs.Union(3, 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
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
91
92
93
94
95
96
97
98
99
100
101
102
103

3相关题目

第一题：剑指 Offer II 116. 省份数量

链接

链接: 剑指 Offer II 116. 省份数量

描述

代码一

class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n,-1)
	{}

	//合并
	void Union(int x1,int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 == root2) return;

		//小的合并大的
		if (root1 > root2) swap(root1, root2);

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	//寻找x的根
	int FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}
		return root;
	}

	//判断是否在一个集合
	bool InSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	//有几个树
	size_t SetSize()
	{
		size_t ret = 0;
		for (int i = 0; i < _ufs.size(); i++)
			if (_ufs[i] < 0) ret++;
		return ret;
	}

private:
	vector<int> _ufs;
};


class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFindSet ufs(isConnected.size());
        for(int i = 0;i<isConnected.size();i++)
        {
            for(int j = 0;j<isConnected.size();j++)
            {
                if(isConnected[i][j]==1)
                    ufs.Union(i,j);
            }
        }
        return ufs.SetSize();
    }
};
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

代码二：

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> ufs(n,-1);

        auto FindRoot = [&ufs](int x)
        {
            while(ufs[x]>=0)
            {
                x=ufs[x];
            }
            return x;
        };

        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if(isConnected[i][j]==1)
                {
                    int root1 = FindRoot(i);
                    int root2=FindRoot(j);
                    if(root1!=root2)
                    {
                        ufs[root1]+=ufs[root2];
                        ufs[root2]=root1;
                    }
                }
            }
        }

        int ret = 0;
        for(auto e:ufs)
        {
            if(e<0) ++ret;
        }
        return ret;
    }
};
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

第二题：990. 等式方程的可满足性

链接

链接: 990. 等式方程的可满足性

题目描述

代码

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        vector<int> ufs(26,-1);

        auto FindRoot = [&ufs](int x)
        {
            while(ufs[x]>=0)
            {
                x=ufs[x];
            }
            return x;
        };

        for(auto& str:equations)
        {
            if(str[1]=='=')
            {
                int root1=FindRoot(str[0]-'a');
                int root2=FindRoot(str[3]-'a');
                if(root1!=root2)
                {
                    ufs[root1]+=ufs[root2];
                    ufs[root2]=root1;
                }
            }
        }

        for(auto& str:equations)
        {
            if(str[1]=='!')
            {
                int root1=FindRoot(str[0]-'a');
                int root2=FindRoot(str[3]-'a');
                if(root1==root2)
                {
                    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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43