题目链接: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; }