解題區/解題區 - UVa

UVa 11870 - Antonyms

contents

  1. 1. Problem
  2. 2. Sample Output
  3. 3. Sample Input
  4. 4. Solution

Problem

告訴你那些是同義詞，以及誰與誰是反義詞，最後回報是否有矛盾情況。

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
big large
small tiny
big small
tiny huge
2 1
xyz abc
abc def
def xyz
1 3
fire flame
fire ice
ice water
water fire

Sample Input

1
2
3
Case 1: YES
Case 2: NO
Case 3: NO

Solution

對於每個詞建立兩個節點 (正反兩種意思的節點)，同義詞則對兩個正做連接，只需要對建造反義祠的時候檢查，查詢每次是否會落在相同集合的操作。

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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <iostream>
using namespace std;
int p[2048], rank[2048];
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)	return 0;
    if(rank[x] > rank[y])
        p[y] = x, rank[x] += rank[y];
    else
        p[x] = y, rank[y] += rank[x];
    return 1;
}
int main() {
    int testcase, cases = 0, N, M;
    char s[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &M);
        map<string, int> R;
        int size = 0;
        for(int i = 0; i < 2048; i++)
            p[i] = i, rank[i] = 1;
        for(int i = 0; i < N; i++) {
            scanf("%s", s);
            int &x = R[s];
            if(x == 0)	x = ++size;
            scanf("%s", s);
            int &y = R[s];
            if(y == 0)	y = ++size;
            joint(2 * x, 2 * y);
        }
        int ret = 1;
        for(int i = 0; i < M; i++) {
            scanf("%s", s);
            int &x = R[s];
            if(x == 0)	x = ++size;
            scanf("%s", s);
            int &y = R[s];
            if(y == 0)	y = ++size;
            if(findp(2 * x) == findp(2 * y))
                ret = 0;
            joint(2 * x + 1, 2 * y);
            joint(2 * y + 1, 2 * x);
        }
        printf("Case %d: %s\n", ++cases, ret ? "YES" : "NO");
    }
    return 0;
}