本来要用并查集的,发现并查集只能解决‘-’还是非‘-’的问题。
干脆直接用dfs搜索一下(这个图非常小 26*26的图)。
如果from到to搜不通,就从to到from再搜一次。
#include<iostream> #include<string> #include<vector> using namespace std; const int maxn=26; vector<int> g[maxn]; int n,m,depth; string s; void print(int d,int flag){ //打印,flag表示是 0表示长辈,1表示孩子,d表示深度depth if(d==1){ cout<<(flag==0?"parent":"child")<<endl; }else if(d==2){ cout<<(flag==0?"grandparent":"grandchild")<<endl; }else{ for(int i=0;i<d-2;i++){ cout<<"great-"; } cout<<(flag==0?"grandparent":"grandchild")<<endl; } } void dfs(int f,int t,int d){ //from to depth if(f==t){ depth=d; return ; } for(int i=0;i<g[f].size();i++){ dfs(g[f][i],t,d+1); } } int main(){ while(cin>>n>>m){ for(int i=0;i<n;i++){ cin>>s; if(s[1]!='-') g[s[0]-'A'].push_back(s[1]-'A'); if(s[2]!='-') g[s[0]-'A'].push_back(s[2]-'A'); } for(int i=0;i<m;i++){ depth=-1; cin>>s; int f=s[0]-'A',t=s[1]-'A'; dfs(f,t,0); if(depth==-1){ //如果第一种搜不通,就按第二种 dfs(t,f,0); if(depth==-1){ cout<<"-"<<endl; }else{ print(depth,0); } }else{ print(depth,1); } } } return 0; }