【四川选拔】亲戚(normal) Time Limit:10000MS  Memory Limit:65536KTotal Submit:4 Accepted:1 Case Time Limit:1000MS Description 　　若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 　　规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 Input 　　第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 　　以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。 　　接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。 Output 　　P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。 Sample Input 　　6 5 3 　　1 2 　　1 5 　　3 4 　　5 2 　　1 3 　　1 4 　　2 3 　　5 6 Sample Output 　　Yes 　　Yes 　　No Source xinyue   g不知道是不是并查集。思路， 针对每一对亲戚关系，找一个最小的编号做为家长。 更新另一个所有有关的家族！ 源代码： #include<stdio.h>int M[5005];int main(){ int n,m,p; int i,a,b,temp,k; scanf("%d %d %d",&n,&m,&p);  for(i=1;i<=5000;i++)  M[i]=i; for(i=1;i<=m;i++) {  scanf("%d %d",&a,&b);  if(M[b]<M[a])  {   temp=M[a];   for(k=1;k<=n;k++)   {   if(M[k]==temp)    M[k]=M[b];   }  }  else   {   temp=M[b];   for(k=1;k<=n;k++)   {    if(M[k]==temp)     M[k]=M[a];   }  } } for(i=1;i<=p;i++) {  scanf("%d %d",&a,&b);  if(M[a]==M[b])   printf("Yes\n");  else printf("No\n"); } return 0;}    

评论