P2814 家谱 map

佚名 6年前 (2019-05-08) 随笔 2093人围观抢沙发百度已收录

题目背景

现代的人对于本家族血统越来越感兴趣。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题目描述

给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

输入输出格式

输入格式：

输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。

输出格式：

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

输入输出样例

输入样例#1：复制

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

输出样例#1：复制

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

可以用并查集做但是用map更加方便注意map是没有传递性的

祖宗是自己的情况要特判

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=50005;

map<string,string>mp;

int main()
{
    string fa;
    string s;
    while(cin>>s)
    {
        if(s=="$")break;
        if(s[0]=='#')
            fa=s.substr(1,s.size()-1);
        else if(s[0]=='+')
        {
            s=s.substr(1,s.size()-1);
            mp[s]=fa;//mp[fa]=fa;
        }
        else if(s[0]=='?')
        {
            s=s.substr(1,s.size()-1);
            cout<<s<<" ";
            if(mp[s]=="")
                cout<<s<<endl;
            else
            {
            while(mp[mp[s]]!="")
                s=mp[s];
            cout<<mp[s]<<endl;
            }
        }
    }
}

View Code

简便一点的写法：

#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
map<string,string>p;
string find(string x)
{
    if(x!=p[x]) 
        p[x]=find(p[x]);
    return  p[x];
}
string s,s1;
int main()
{
    char ch;
    cin>>ch;
    while(ch!='$')
    {
        cin>>s;
        if(ch=='#')
        {
            s1=s;
            if(p[s]=="") p[s]=s;
        }
        else if(ch=='+')
            p[s]=s1;
        else 
            cout<<s<<' '<<find(s)<<endl;    
        cin>>ch;
    }
    return 0;
}