D. Mahmoud and a Dictionary
链接：
http://codeforces.com/contest/766/problem/D
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 using namespace std; 9 const int MAXN = 100005; 10 map<string, int>mp; 11 int getId(string str) 12 { 13 if (!mp[str])mp[str] = (int)mp.size(); 14 return mp[str]; 15 } 16 int fa[MAXN], w[MAXN]; 17 void Init(int n) 18 { 19 for (int i = 1; i <= n; i++) 20 fa[i] = i, w[i] = 0; 21 } 22 int Find(int x) 23 { 24 if (x != fa[x]) 25 { 26 int rt = Find(fa[x]); 27 w[x] ^= w[fa[x]]; 28 fa[x] = rt; 29 } 30 return fa[x]; 31 } 32 int Union(int x, int y, int v) 33 { 34 int rx = Find(x), ry = Find(y); 35 if (rx == ry)return -(w[x] ^ w[y] ^ v); 36 fa[rx] = ry, w[rx] = w[x] ^ w[y] ^ v; 37 return 1; 38 } 39 int main() 40 { 41 int n, m, q; 42 scanf("%d%d%d", &n, &m, &q); 43 for (int i = 1; i <= n; i++) 44 { 45 char s[25]; 46 scanf("%s", s); 47 getId(s); 48 } 49 Init(n); 50 for (int i = 1; i <= m; i++) 51 { 52 int r; 53 char s[25], t[25]; 54 scanf("%d%s%s", &r, s, t); 55 int tmp = Union(getId(s), getId(t), r - 1); 56 printf("%s ", (tmp<0 ? "NO" : "YES")); 57 } 58 for (int i = 1; i <= q; i++) 59 { 60 char s[25], t[25]; 61 scanf("%s%s", s, t); 62 int x = getId(s), y = getId(t); 63 int rx = Find(x), ry = Find(y); 64 printf("%d ", (rx == ry ? (w[x] ^ w[y] ? 2 : 1) : 3)); 65 } 66 return 0; 67 }