首页 > 代码库 > 畅通工程&&How Many Tables

畅通工程&&How Many Tables

2024-07-10 03:14:39   214人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1232

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <stdlib.h> 5 using namespace std; 6 int n,m; 7 int bin[2005]; 8 int findx(int x) 9 {10     int r=x;11     while(bin[r]!=r)12     {13         r=bin[r];14     }15     int k,j;16     k=x;17     while(k!=r)18     {19         j=bin[k];20         bin[k]=r;21         k=j;22     }23     return r;24 }25 void merge(int x,int y)26 {27     int fx=findx(x);28     int fy=findx(y);29     if(fx!=fy)30     bin[fx]=fy;31 }32 int main()33 {34     int x,y;35     while(scanf("%d",&n)!=EOF&&n!=0)36     {37         scanf("%d",&m);38         for(int i=1;i<=n;i++)39             bin[i]=i;40         while(m--)41         {42             scanf("%d%d",&x,&y);43             merge(x,y);44         }45         int l=0;46         for(int i=1;i<=n;i++)47         {48             if(findx(i)==i)49                 l++;50         }51 52         printf("%d\n",l-1);53 54 55     }56     return 0;57 }

不知道为么，这样就WA

if(findx(x)!=findx（y))

merge(x,y);

http://acm.hdu.edu.cn/showproblem.php?pid=1213

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <stdlib.h> 5 using namespace std; 6 int n,m; 7 int bin[2005]; 8 int findx(int x) 9 {10     int r=x;11     while(bin[r]!=r)12     {13         r=bin[r];14     }15     int k,j;16     k=x;17     while(k!=r)18     {19         j=bin[k];20         bin[k]=r;21         k=j;22     }23     return r;24 }25 void merge(int x,int y)26 {27     int fx=findx(x);28     int fy=findx(y);29     if(fx!=fy)30     bin[fx]=fy;31 }32 int main()33 {34     int x,y;35     int T,K=0;36     scanf("%d",&T);37     while(T--)38     {39         K++;40         scanf("%d%d",&n,&m);41         for(int i=1;i<=n;i++)42             bin[i]=i;43         while(m--)44         {45             scanf("%d%d",&x,&y);46             merge(x,y);47         }48         printf("\n");49         int l=0;50         for(int i=1;i<=n;i++)51         {52             if(findx(i)==i)53                 l++;54         }55         printf("%d\n",l);56        57     }58     return 0;59 }

 


联系
我们