ACM-NEFUOJ-P210畅通工程并查集

本文最后更新于:2020年12月19日 下午

题目:我已经明示到这个程度了你还不用并查集?

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

using namespace std;

const int MAXN=1010;

int F[MAXN];

int GetFather(int x)
{
return F[x]==x?x:F[x]=GetFather(F[x]);
}

void Union(int a,int b)
{
int t1=GetFather(a);
int t2=GetFather(b);
if(t1!=t2) F[t1]=t2;
}

int main()
{
int n,m;

while(cin>>n&&n)
{
cin>>m;
for(int i=1;i<=n;i++) F[i]=i;
int a,b;
while(m--)
{
cin>>a>>b;
Union(a,b);
}
int res=0;
for(int i=1;i<=n;i++)
if(F[i]==i) res++;
printf("%d\n",res-1);
}
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!