访问次数：

并查集基础题hdu1232畅通工程详解附带模板 | Wenji's blog
头部背景图片
WenJi's blog |
WenJi's blog |

并查集基础题hdu1232畅通工程详解附带模板

2018-09-21
#并查集 
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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring> 
using namespace std;
int pre[1010];
int flag[1010];//判断是否是根节点 
int find(int x)
{
	int r=x;
	while(pre[r]!=r)
	{
		r=pre[r];
	}
	int i=x;
	int j;
	while(i!=r)			//路径压缩 
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}
void join(int x,int y)			//判断是否均为联通分支，并且进行合并 
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		pre[fx]=fy;
	}
}
int main()
{
	int N,M;
	int a,b;
	int total;
	while(scanf("%d%d",&N,&M)&&N)
	{
		for(int i=1;i<=N;i++)
		{
			pre[i]=i;
		}
		for(int i=1;i<=M;i++)
		{
			
			scanf("%d%d",&a,&b);
			join(a,b);
		}
		memset(flag,0,sizeof(flag));
		for(int i=1;i<=N;i++)
		{
			int gen=find(i);
			flag[gen]=1;
		}
		total=0;
		int shu=0;//根节点的数目 
		for(int i=1;i<=N;i++)
		{
				if(flag[i])
				{
					shu++;
				} 
		}
		total=shu-1;//易错，不能写成shu--,因为运算的优先性 
		printf("%d\n",total);
	} 
	return 0;
}

contest1 rumor 并查集基础变式练习

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
typedef long long ll;
using namespace std;
int pre[100010];
ll gold[100010];
int vis[100010];//判断是否是根节点 
int find(int x)
{
	int r=x;
	while(pre[r]!=r)
	{
		r=pre[r];
	}
	int i=x,j;
	while(i!=r)
	{
		j=pre[i];
		pre[i]=r;//易错，不是r=pre[i],而是pre[i]=r; 
		i=j;
	}
	return r;
}
void join(int a,int b)
{
	int fx=find(a);
	int fy=find(b);
	if(fx!=fy)
	{
			pre[fx]=fy;
	}
}
int main()
{
	int N,M;
	ll total;
	while(cin>>N>>M)
	{
	 	for(int i=1;i<=N;i++)
	 	{
	 		cin>>gold[i];//lld的输入不用scanf,而是用cin,或者是%I64d这样。 
		}
		for(int i=1;i<=N;i++)
		{
			pre[i]=i;
		} 
		for(int i=1;i<=M;i++)
		{
			int a,b;
			cin>>a>>b;
			join(a,b);
		}
		memset(vis,0,sizeof(vis)); 
		for(int i=1;i<=N;i++)
		{
			int gen=find(i);
			vis[gen]=1;
			gold[gen]=min(gold[gen],gold[i]);//本题易错，这里是一个易错点。 
		}
		total=0;
		for(int i=1;i<=N;i++)
		{
			if(vis[i])
			{
				total+=gold[i];
			}
		}
		cout<<total<<endl; 
	}
	return 0;
}