题解 | #第一题#

#include <stdio.h>
#并查集
typedef struct
{
    int x;
    int y;
} Line;
int getEnd(int x,int root[])
{
    int n=x;
    while(root[n]!=0)n=root[n];
    //printf("n:%d\n",n);
    return n;
}
int main() {
   int a,b;
   Line line[2000000];
   int i=0;
   while (scanf("%d %d",&a,&b)!=EOF) {
        line[i].x=a;
        line[i].y=b;
        i++;
   }
   int root[2000000]={0};
   int mark[2000000]={0};
   for(int j=0;j<i;j++)
   {
    int end1=getEnd(line[j].x,root);
    int end2=getEnd(line[j].y,root);
    if(end1!=end2)
    {
        root[end2]=end1;
    }
        //printf("x:%d,y:%d,end1:%d,end2:%d,root[end2]:%d\n",line[j].x,line[j].y,end1,end2,root[end2]);
    if(end1==line[j].y&&root[end2]==0)root[line[j].x]=line[j].y;
        //printf("@@@@@@@@@@@\n");
   }
    for(int j=1;j<2000000;j++)
    {
        if(root[j]!=0&&root[j]!=j)root[j]=getEnd(root[j],root);
    }
   int flag=0;
   for(int j=1;j<2000000;j++)
   {
    if(mark[root[j]]==0&&root[j]!=0)
    {
        mark[root[j]]=1;
        //printf("%d\n",root[j]);
        flag++;
    }
   }
   printf("%d",flag);

   return 0;
}