畅通工程 简单并查集

畅通工程

畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19157    Accepted Submission(s): 9848

Problem DescriptionInputOutputSample InputSample Output

并查集
刚开始的先赋初值
for(int i=1;i<=N;i++)
每个点只指向自己
每输入一条边进行操作
例如：
输入1---2这条边  merger(1,2);
find(1)=1;find(2)=2; 则赋为f[1]=f[2]=1;
输入1---3这条边  merger(1,3);
find(1)=1;find(3)=3;  f[1]=f[3]=1;
输入2---3这条边  merger(2,3);
find(1)=1;find(3)=1;  f[2]=f[3]=1;
初始：1 2 3    结束：1 2 3
      1 2 2          1 1 1

 

 

#include<cstdio>#include<cstring>using namespace std;int f[1001];int find(int x){    if(x==f[x])        return x;    return find(f[x]);}void merge(int x,int y){    int a;    int b;    a=find(x);    b=find(y);    if(a==b) return ;    else    f[a]=f[b]=a;}int main(){    int N,M;    while(scanf("%d",&N)!=EOF)    {        memset(f,0,sizeof(f));        if(N==0)  break;        for(int i=1; i<=N; i++)            f[i]=i;        scanf("%d",&M);        int x,y;        for(int i=0; i<M; i++)        {               scanf("%d%d",&x,&y);               merge(x,y);        }        int sum=-1;        for(int i=1;i<=N;i++)        {            if(f[i]==i)            sum++;        }        printf("%d\n",sum);    }    return 0;}