【3.16高一（第二学期）模拟测试】 T3，T4题解

　　看到这个标题我想你一定会想为什么小编只发T3，T4的题解，原因有很多：1）小编也不怎么会讲；2）小编搜遍各大OJ，都没有找到可以提交的地方；3）虽然给了测试数据，小编懒得一个一个试。如果你找到了测评网址，欢迎留言。

先说T3，题目如下：

C、团伙 
【问题描述】
    TEIAI 集团共有 n 名员工，编号为 1~n。由于长期的权力斗争，他们形成了
复杂的势力网络。对于任意两名员工，他们可能是朋友，可能是敌人，也可能没
什么关系。并且这种关系满足：（1）朋友的朋友是我的朋友；（2）敌人的敌
人也是我的朋友。为了抱团取暖，党同伐异，员工们形成了若干团伙，每个团伙
均满足：团伙内的所有人互为朋友，团伙外的每个人都不是朋友。
 集团的高层认为，这种斗争关系可以加速优胜劣汰的过程，从而促进集团的
盈利。他们通过暗访得到了这样的 m 条信息：每条信息包含 3 个值 p，x，y，
p=F 表示员工 x 与 y 是朋友，p=E 表示员工 x 与 y 是敌人。请你根据这 m 条信
息，判断这些员工最多可能形成多少个团伙？
【输入格式】
  第 1 行为 n 和 m，1<n<1000,1<=m<=5000；
  以下 m 行，每行为 pxy。
【输出格式】
  一个整数，表示这 n 个人最多可能有几个团伙。
【输入样例】 
  64
  E14
  F35
  F46
  E12
【输出样例】 
3
【样例说明】{1},{2,4,6},{3,5}

　　看起来这道题需要好好思索一番，此题一看就知道必须要用并查集（不会点这里）。首先，题目中出现了两种关系，分别是朋友关系和敌人关系，那么就要分类讨论了，先看朋友关系，这个好说，直接合并就可以了；那么敌人关系呢？根据敌人的敌人是朋友这个条件，只需要分别把敌人和另一个敌人的敌人合并即可。

代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 int n,m,p,q,a[10000],ans=0,num[10000];char c,ch;
 4 int find(int x)//并查集
 5 {
 6     if(x==a[x]) return x;
 7     else return a[x]=find(a[x]);
 8 }
 9 int main()
10 {
11     //freopen("group.in","r",stdin);
12     //freopen("group.out","w",stdout);
13     cin>>n>>m;
14     for(int i=1;i<=n*2;i++) a[i]=i;//为了后续操作更方便，将1~n存为每一个人的祖先，n+1~n+n为1~n每个人的敌人，例如1和1+n是敌人关系
15     for(int i=1;i<=m;i++)
16     {
17         cin>>c;
18         cin>>p>>q;
19         if(c=='F') a[find(p)]=find(q);//朋友关系直接合并
20         else
21         {
22              a[find(p+n)]=find(q);//将敌人与敌人的敌人合并
23             a[find(q+n)]=find(p);//同上
24         }
25     }
26     for(int i=1;i<=n;i++)
27     if(a[i]==i) ans++;//判断有多少个祖先即可知道有多少个团伙
28     cout<<ans;
29     return 0;
30 }

T4，题目如下：

D、家谱 
【问题描述】 
给定一系列父子关系，求某些人的祖先。“祖先”指的是从该人开始，沿父
子关系向上追溯可以达到的辈分最大的人。
【输入格式】 
每行包含一个人名和一个标识符。标识符紧贴在名字的前面，不同标识符的
含义如下：（人名用 Name 指代）
#Name：从下一行开始，每一个以标识符+开头的人名都是 Name 的儿子，
直至遇到第一个不以+开头的人名；
+Name：上一个用#标识的人的儿子；
?Name：要求输出 Name 的祖先。
最后一行用一个字符$表示输入结束。
【输出格式】
按照输入文件的要求顺序，求出每一个用?标识的人的祖先，格式：本人的
名字+一个空格+祖先的名字+回车。
【输入样例】 
    #George
    +Rodney
    #Arthur
    +Gareth
    +Walter
    #Gareth
    +Edward
    ?Edward
    ?Walter
    ?Rodney
    ?Arthur
    $
【输出样例】 
    EdwardArthur
    WalterArthur
    RodneyGeorge
    ArthurArthur
【数据规模】 
 输入文件的总行数≤200,000。

　　这道题与之前T3一样，需要用到并查集，但是合并是一件很麻烦的事情，如果装换成序号来做就太麻烦了，还会出现各种不必要的麻烦。那么就要请出传奇的map了。

　　map是什么呢？用东西总得加头文件吧，要加上#include<map>才能用，map主要用来使两个元素发生联系，并且这两个元素可以是任意类型，这样数组下标就可以用string了。

代码如下：

#include<iostream>
#include<cstring>
#include<map>
using namespace std;
map<string,string>a;//尖括号内的两种类型可以分别当成数组下标与数组值的类型 
string c,s;char ch;
string find(string x)//字符串+并查集 
{
    if(a[x]==x) return x;
    else return a[x]=find(a[x]);
}
int main()
{
    for(;;)
    {
        cin>>ch;
        cin>>c;
        if(ch=='$') break;
        else if(ch=='#')
        {
            s=c;
            if(a[s]=="") a[s]=s;//如果s没有爹，那么就只能让s叫自己爹了 
        }
        else if(ch=='+') a[c]=s;
        else cout<<c<<" "<<find(c)<<endl;
    }
    return 0;
}