欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【TOJ 3660】家庭关系(map映射的并查集)

程序员文章站 2022-03-27 21:07:20
描述 给定若干家庭成员之间的关系,判断2个人是否属于同一家庭,即2个人之间均可以通过这些关系直接或者间接联系。 给定若干家庭成员之间的关系,判断2个人是否属于同一家庭,即2个人之间均可以通过这些关系直接或者间接联系。 输入 输入数据有多组,每组数据的第一行为一个正整数n(1<=n<=100),表示有 ......

描述

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