题目链接：http://codeforces.com/contest/766/problem/D
题意：给你n个单词,m个关系(两个单词是反义词还是同义词)，然后问你所给的关系里面有没有错的，最后再给你q个询问,问你两个单词之间的关系是什么，
同义词输出1,反义词输出2,不确定输出3;
其实就是种类并查集。种类并查集怎么做之前的随笔中有说过。
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int M = 1e5 + 10;
int f[M] , root[M] , n , m;
void init() {
for(int i = 1 ; i <= n ; i++) {
f[i] = i , root[i] = 0;
}
}
int find(int x) {
if(x == f[x])
return x;
int tmp = find(f[x]);
root[x] = (root[x] + root[f[x]]) % 2;
return f[x] = tmp;
}
string s , s1 , s2;
map<string , int>mmp;
int main() {
int x , y , num , q;
cin >> n >> m >> q;
init();
for(int i = 0 ; i < n ; i++) {
cin >> s;
mmp[s] = i + 1;
}
for(int i = 1 ; i <= m ; i++) {
cin >> num >> s1 >> s2;
x = mmp[s1] , y = mmp[s2];
int t1 = find(x) , t2 = find(y);
if(num == 1) {
if(t1 == t2) {
if(root[x] != root[y]) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
else {
cout << "YES" << endl;
f[t1] = t2;
root[t1] = root[y] - root[x];
root[t1] = (root[t1] + 2) % 2;
}
}
else {
if(t1 == t2) {
if(root[x] == root[y]) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
else {
cout << "YES" << endl;
f[t1] = t2;
root[t1] = (root[y] + 1 - root[x]);
root[t1] = (root[t1] + 2) % 2;
}
}
}
while(q--) {
cin >> s1 >> s2;
x = mmp[s1] , y = mmp[s2];
int t1 = find(x) , t2 = find(y);
if(t1 == t2) {
if(root[x] == root[y]) {
cout << 1 << endl;
}
else {
cout << 2 << endl;
}
}
else {
cout << 3 << endl;
}
}
return 0;
}