【TOJ 3660】家庭关系（map映射的并查集）

描述

给定若干家庭成员之间的关系，判断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;
}