描述
给定若干家庭成员之间的关系，判断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<bits/stdc++.h> #define MAX 10005 using namespace std; int p[MAX]; int find(int r) { if(p[r]!=r) p[r]=find(p[r]); return p[r]; } void join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) p[fx]=fy; } void init() { for(int i=0;i<=MAX;i++) p[i]=i; } int main() { string a,b,c; int n; while(cin>>n,n) { init(); map<string,int>ma; int cnt=1; while(n--) { cin>>a>>b>>c; if(ma[a]==0) ma[a]=cnt++; if(ma[b]==0) ma[b]=cnt++; if(ma[c]==0) ma[c]=cnt++; join(ma[a],ma[b]); join(ma[a],ma[c]); } cin>>a>>b; if(m[a]!=0&&m[b]!=0&&find(m[a])==find(m[b])) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
