Rainy-白红宇

Rainy

阅读量：7088 次

发布时间：2019-06-28

本文共 952 字，大约阅读时间需要 3 分钟。

今天bin哥讲了一下并查集

怎么说，tql，像我这种没学树啥也没学的人竟然听懂了（捂脸，讲的太好了

洛谷 P2814 家谱

题目描述

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

输入格式：

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

输出格式：

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

然后代码不是自己写的qwq 写这个就是记一下过程害怕以后又忘了orz

#include
     
      #include
      
       #include
       using namespace std;map
        
         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<
         <<' '<
          
           <
           
            >ch; } return 0;}

总之讲的太好了！//学姐讲的也很好qwq

转载于:https://www.cnblogs.com/Grigory/p/10055201.html

你可能感兴趣的文章