1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstring>
#include <map>
#include <iostream>
#include <vector>
using std::cin;
using std::map;
using std::string;
using std::vector;
const int MAXN = 100000, MAXM = 100000;
string names[2 * MAXN];
int union_find_set[2 * MAXN], father[2 * MAXN],
    request_content[MAXN + 1], request_answer[MAXN + 1],
    spring_head[2 * MAXN], spring_next[2 * MAXN];
bool request_visited[MAXN + 1];
map<string, int> idx;  /*这里命名为index就会Compile Error，闹哪样*/
vector<int> requests[MAXN + 1];
/*由于每个request属于两个名字，不能再使用head+next写单链表，此处使用vector
 *request_visited初始化为false，表示某个request是否曾经被访问过
 *request_content存放每个request两个name的index的异或结果，便于求出另一个name
 *spring编号必为正整数，初始化为0，保存每个节点的孩子，用于DFS*/
int get_father(int x) {
    if (x == union_find_set[x])
        return x;
    else
        return (union_find_set[x] = get_father(union_find_set[x]));
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX