Codeforces 766D - Mahmoud and a Dictionary

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n\)个单词，\(m\)个关系，\(q\)个询问，每个关系有如下情况

  • \(1 \space x \space y\)，表示\(x\)和\(y\)是近义词；
  • \(2 \space x \space y\)，表示\(x\)和\(y\)是反义词。

对于关系，如果关系与之前的关系不冲突，输出“YES”；否则，输出“NO”。每个询问，给出两个单词，输出二者的关系，1、2、3分别代表近义词、反义词、没有关系。

思路

图的题做的不多，但看这个题第一反应就是并查集。看了题解做的，感觉是道不错的题。用异或和表示两个单词的关系，在Find中维护当前节点\(x\)和\(p[x]\)的关系。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

typedef long long LL;

const int maxn = 200010;
int p[maxn], a[maxn];
char s[maxn];
vector<int> g[maxn];
map<string, int> dict;

int Find(int x) {
  if (x == p[x]) {
    return x;
  }
  int px = p[x];
  p[x] = Find(p[x]);
  a[x] ^= a[px];
  return p[x];
}

bool Union(int u, int v, int x) {
  int fu = Find(u), fv = Find(v);
  if (fu == fv) {
    return (a[u] ^ a[v]) == x;
  }
  p[fu] = fv;
  a[fu] = a[u] ^ a[v] ^ x;
  return true;
}

int Query(int u, int v) {
  int fu = Find(u), fv = Find(v);
  if (fu == fv) {
    return (a[u] ^ a[v]) + 1;
  }
  return 3;
}

int getID() {
  scanf("%s", s);
  return dict[s];
}

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s);
    dict[s] = p[i] = i;
    a[i] = 0;
  }
  while (m--) {
    int x;
    scanf("%d", &x);
    puts(Union(getID(), getID(), x - 1) ? "YES" : "NO");
  }
  while (q--) {
    printf("%d\n", Query(getID(), getID()));
  }
  return 0;
}
相关文章