解題區►解題區 - 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;
}