c++并查集配合STL MAP的实现（洛谷P2814题解）

不会并查集的话请将此文与我以前写的并查集一同食用。

原题来自洛谷

原题

文字稿在此：

题目背景

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

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

#George

+Rodney

#Arthur

+Gareth

+Walter

#Gareth

+Edward

?Edward

?Walter

?Rodney

?Arthur

$

输出样例#1：

Edward Arthur

Walter Arthur

Rodney George

Arthur Arthur

说明

规定每个人的名字都有且只有6个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。

map

map是STL中的一种数据结构，你可以理解为它是一个下表不一定 为整形的数组（也就是说，下表可以为字符、字符串。。。）

map类型的声明

大体模式式是

map<下标类型，数组每一个元素的类型> 数组名;

比如说我要一个下表是字符串，每一个元素的类型也是字符串，名字叫a的数组，我可以这样写

map<string,string> a;

回到题目

会了map，相信你应该也有点思路了吧？这是 建立在并查集基础上的，不会并查集的话，可以看看我以前写的并查集。

有了map我们就可以使用 真正意义上的字符串数组来编程了！！！

函数

这里面的getfather函数 变异了，他成了这样

string getfather(string x)//找x的根结点

{//这其实是一个递归函数

	if(father[x]!=x)

	{

		return getfather(father[x]);//它会一级一级找上去（先找到它爸爸，在找到它爸爸的爸爸，再找到它爸爸的爸爸的爸爸。。。。。）

	}

	else

	{

		return father[x];//边界条件，如果x的根结点就是x（也就是说它没有更上边的祖宗了）

	}

}

相较以前的getfather，首先函数的类型成了string，而且x的类型也是string。但是作用和以前是一样的。

读入

这题的读入很特殊，因为这道题要边读入边处理边输出

char c;//就是名字 前面那个字符

string s,fat;//s是名字，fat是是用来暂存先提及的父亲的名字的

这题我用了这几个变量。

核心代码如下

map<string,string> father;//用来存储某一点的根结点

    cin>>c;//读入c

    while(c!='$')//只要c不是$就会执行

    {

        cin>>s;//读入名字

        if(c=='#')//假如读到了父亲 的名字

        {

            fat=s;//fat暂存父亲的名字，因为过一会儿s的值会变

            if(father[s]=="")    father[s]=s;//如果father[s]的值为空，也就是说s就是自己的根结点（找到底了）

        }

        if(c=='+')//如果s是表示儿子

        {

            father[s]=fat;//s的根结点就成了fat（上面说的fat这是就派上了用场）

        }

        if(c=='?')//查集

        {

            cout<<s<<' '<<getfather(father[s])/*输出father[s]的根结点*/<<endl;

        }

        cin>>c;//读入c，开始新一轮的循环

    }

完整程序如下

#include<map>

#include<iostream>

using namespace std;

map<string,string> father;

string getfather(string x)

{

	if(father[x]!=x)

	{

		return getfather(father[x]);

	}

	else

	{

		return father[x];

	}

}

int main()

{

	char c;

	string s,fat;

	cin>>c;

    while(c!='$')

    {

        cin>>s;

        if(c=='#')

        {

            fat=s;

            if(father[s]=="")    father[s]=s;

        }

        if(c=='+')

        {

            father[s]=fat;

        }

        if(c=='?')

        {

            cout<<s<<' '<<getfather(father[s])<<endl;

        }

        cin>>c;

    }

    return 0;

}

总结

这题其实和并查集的模版的差异并不大，只是涉及到STL中的数据结构map的使用。所以对于提高+的评价感觉是过了点，但要是不会map的话可能真的是这个难度了。

如果字符串功底够好，也可以 考虑用字符串/字符 数组来实现（我字符串功底不好。。）

tks。

c++并查集配合STL MAP的实现（洛谷P2814题解）的相关教程结束。