将辈分差距转为数字
例如 A 是 B son
A=B-1
A 是 B grandfather
A=B+2
然后编号1数字设置为0,建图bfs
最后搜索编号2到100是否存在>0的数即可
1 /* 2 Written By. StelaYuri 3 On 2020/01/15 4 */ 5 #include<bits/stdc++.h> 6 using namespace std; 7 typedef pair<int,int> P; 8 vector<P> v[105]; 9 queue<int> q; 10 int dis[105]; 11 bool vis[105]; 12 int main(){ 13 memset(dis,0x3f,sizeof dis); 14 int N,i,now,cnt,a,b; 15 char s[15]; 16 scanf("%d",&N); 17 while(N--){ 18 scanf("%d is %d's %s",&a,&b,s); 19 if(strcmp(s,"father.")==0){ 20 v[a].push_back(P(b,-1)); 21 v[b].push_back(P(a,1)); 22 } 23 else if(strcmp(s,"son.")==0){ 24 v[a].push_back(P(b,1)); 25 v[b].push_back(P(a,-1)); 26 } 27 else if(strcmp(s,"brother.")==0){ 28 v[a].push_back(P(b,0)); 29 v[b].push_back(P(a,0)); 30 } 31 else if(strcmp(s,"grandson.")==0){ 32 v[a].push_back(P(b,2)); 33 v[b].push_back(P(a,-2)); 34 } 35 else if(strcmp(s,"grandfather.")==0){ 36 v[a].push_back(P(b,-2)); 37 v[b].push_back(P(a,2)); 38 } 39 } 40 vis[1]=true; 41 dis[1]=0; 42 q.push(1); 43 while(!q.empty()){ 44 now=q.front(); 45 q.pop(); 46 cnt=v[now].size(); 47 for(i=0;i<cnt;i++) 48 if(!vis[v[now][i].first]){ 49 vis[v[now][i].first]=true; 50 dis[v[now][i].first]=dis[now]+v[now][i].second; 51 q.push(v[now][i].first); 52 } 53 } 54 bool flag=true; 55 for(i=2;i<=100;i++) 56 if(dis[i]!=0x3f3f3f3f&&dis[i]>0){ 57 flag=false; 58 break; 59 } 60 puts(flag?"2333333...":"ku jiu ru hou xin zuo tong."); 61 62 return 0; 63 }