友心人 2018-03-21
描述
给定若干家庭成员之间的关系,判断2个人是否属于同一家庭,即2个人之间均可以通过这些关系直接或者间接联系。
输入
输入数据有多组,每组数据的第一行为一个正整数n(1<=n<=100),表示有100个关系描述,接下来有n行,每行的描述方式为:
p1 p2 c
其中p1、p2和c均为一串文本,表示每个人的姓名,p1和p2为c的父亲和母亲。
最后一行包含2个字符串a和b,为待判断的两个人的姓名。
每个人的姓名由大小写字母组成,长度不超过80。
若n为0,表示输入结束。
输出
如果a和b在同一个家庭中,则输出Yes
否则输出No
样例输入
2
Barbara Bill Ted
Nancy Ted John
John Barbara
3
Lois Frank Jack
Florence Bill Fred
Annie Fred James
James Jack
0
样例输出
Yes
No
#include<iostream> #include<algorithm> #include<map> using namespace std; int p[10005]; int find(int r) { if(p[r]!=r) p[r]=find(p[r]); return p[r]; } int join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) p[fx]=fy; } int main() { string a,b,c; int n; while(cin>>n,n) { for(int i=0;i<=10000;i++) p[i]=i; map<string,int>m; int cnt=1; while(n--) { cin>>a>>b>>c; if(m[a]==0) m[a]=cnt++; //映射,若该名字没出现过,依次映射为1、2、3、4…… if(m[b]==0) m[b]=cnt++; if(m[c]==0) m[c]=cnt++; join(m[a],m[b]); join(m[a],m[c]); } /* for(int i=1;i<cnt;i++) //cout<<p[i]<<" "; cout<<endl; for(int i=1;i<cnt;i++) cout<<find(p[i])<<" "; cout<<endl; */ cin>>a>>b; if(m[a]!=0&&m[b]!=0&&find(m[a])==find(m[b])) //a和b名字必须出现过 cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }