这是个虚假的title;并查集

发表于

并查集之前学过，但是没完全理解，之前像写想写博客就好好想了一下感觉理解更深了。。。写博客还是好处很多的。。。

并查集的主要是建立一个类似于是的东西（个人感觉）然后寻根。。
不同的人可以有不同的根 一个并查集里面可以有很多个根！！！这个很重要！！！！有很多根！！！！
他有好几个部分组成第一个find根

1
2
3
int find(int x) {
	return x == pa[x] ? x:pa[x] = find(pa[x]);
}

寻找他的这个数的根一便于后面判断。。。。
然后输unite合并个数，如果他们同根就不合并不同根就合并
1
2
3
4
5
6
7
8
9
10
11
void unite(int a,int b) {
	int x = find(a);
	int y = find(b);
	if(x != y) {
		if(ran[x] > ran[y]) pa[y] = x;
		else {
			pa[x] = y;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
}

这里其实有个优化机库是ran数组用来存储每个树的高度将低的树接到高的树上面可以很有效的减少数的高度，一遍减少find的时耗。

题目：
现在给你 N 个地点 ，和 M 条边 ，表示某两个地点相连( 即无向 ，可以互相通过 ) , 现在希望你判断是否每个地点都能到最后一个点 N 。

这里就可以用到并查集
以下是代码

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
#include<bits/stdc++.h>

using namespace std;

int par[10000];

int n,m;

int find(int x)
{
	return x == par[x] ? x : par[x] = find(par[x]);
}

void in(){
	int i = 1;
	for(i;i <= n;i++)
	{
		par[i] = i;
	}
}

void unite(int a,int b)
{
	find(a) == find(b) ?  : par[find(a)] = find(b);
}

int main()
{
	cin >> n >> m;
	int i;
	int a,b;
	in();
	for(i = 0;i < m;i++)
	{
		cin >> a >> b;
		unite(a,b);
	}
	for(i = 1;i < n;i++)
	{
		find(i) == find(n) ? cout<<"Yes":cout<<"No";
		cout<<endl;
	}
	return 0;
}

这里就是找两个数同不同根
题目2：
众所周知，在电影中总会出现如下的情景：在某个地方有n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友； 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

这个题目就是寻找有几个根的开始先把朋友合起来，再将敌人的敌人合起来
以下是代码

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
#include<iostream>
using namespace std;

int pa[1100];
int ran[1100];
int en[1100][1100];
bool mark[1100];

int find(int x) {
	return x == pa[x] ? x:pa[x] = find(pa[x]);
}

void unite(int a,int b) {
	int x = find(a);
	int y = find(b);
	if(x != y) {
		if(ran[x] > ran[y]) pa[y] = x;
		else {
			pa[x] = y;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
}

int main() {
	int n,m;
	cin >> n >> m;
	int num,num1;
	char judge;
	int i  = 0;
	for(i;i <= n;i++) pa[i] = i;
	for(i = 0; i < m; i++) {
		cin >> judge >> num >> num1;
		switch(judge) {
			case 'F':
				unite(num,num1);
				break;
			case 'E':
				en[num][++en[num][0]] = num1;
				en[num1][++en[num1][0]] = num;
				break;
		}
	}
	int j;
	for(i = 1; i <= n; i++) {
		num = en[i][0];
		for(j = 1; j <= num; j++) {
			int num1 = en[i][j];
			if(j > 1)
				unite(en[i][j],en[i][j - 1]);
			for(int k = 1; k <= en[num1][0]; k++)
				unite(i,en[num1][k]);
		}
	}
	int total = 0;
	for(i = 1; i <= n; i++) {
		num = find(i);
		if(!mark[num]) {
			mark[num] = true;
			total++;
		}
	}
	cout<<total;
	return 0;
}