一开始想用暴力求解,想了半天没有思路..
其实用并查集好多了:
#include<stdio.h> #include<string.h> int find(int array[],int x,int y) { int k=0,mark=0; while(array[x] > 0) { k++; if(array[x]==y){mark=1;break;} x=array[x]; } if(mark) return k; else return 0; } int main() { int child[27]; int i,k,j,flag,tmpflag; char strchild[10],relation[10]; while(1) { scanf("%d%d",&i,&k); if(!i&&!k)break; scanf("\n"); for(j=1;j<=26;j++) child[j]=0; while(i--) { gets(strchild); if(strchild[1] != '-') child[strchild[1]-'A'+1] =strchild[0]-'A'+1; if(strchild[2] != '-') child[strchild[2]-'A'+1] =strchild[0]-'A'+1; } while(k--) { gets(relation); flag = find(child,relation[0]-'A'+1,relation[1]-'A'+1); tmpflag = find(child,relation[1]-'A'+1,relation[0]-'A'+1); if(!flag&&!tmpflag)printf("-\n"); else if(flag&&!tmpflag) { while(flag>2) { printf("great-"); flag--; } if(flag==2)printf("grandparent\n"); else if(flag==1)printf("parent\n"); } else if(!flag&&tmpflag) { while(tmpflag>2) { printf("great-"); tmpflag--; } if(tmpflag==2)printf("grandchild\n"); else if(tmpflag==1)printf("child\n"); } } } return 0; }