*union find set을 사용해서 진실을 알고 있는 사람들끼리 한 세트로 만들었다.
**dp로 풀어보기 **
*도움이 된 TC
4 3
1 2
2 1 2
1 3
3 2 3 4
ans = 0
5 3
1 3
3 1 2 4
3 1 4 5
1 3
ans = 2
3 2
1 1
2 2 3
2 1 2
ans = 0
6 5
1 6
2 4 5
2 1 2
2 2 3
2 3 4
2 5 6
ans = 0
6 5
1 6
2 1 2
2 2 3
2 3 4
2 4 5
2 5 6
ans = 0|
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
//거짓말
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int parent[51];
int unionSize[51];
bool isKnow[51] = {0};
int find(int a) {
if (parent[a] == a) return a;
return parent[parent[a]] = find(parent[a]);
}
void union_find(int a, int b) {
int pA = find(a);
int pB = find(b);
if (pA == pB) return;
if (unionSize[pA] >= unionSize[pB]){
parent[pB] = pA;
unionSize[pA] += unionSize[pB];
unionSize[pB] = 0;
}
else {
parent[pA] = pB;
unionSize[pB] += unionSize[pA];
unionSize[pA] = 0;
}
}
bool isSame(int a, int b) {
int pA = find(a);
int pB = find(b);
if (pA == pB) return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
unionSize[i] = 1;
}
int truth;
cin >> truth;
int number;
cin >> number;
isKnow[number] = true;
for (int i = 1; i < truth; i++)
{
int tmp;
cin >> tmp;
isKnow[tmp] = true;
union_find(number, tmp);
}
if (truth == 0) //진실을 아는 사람이 없어서 매번 거짓말을 해도 된다.
cout << m << '\n';
else
{
//어떤 사람이 어떤 파티에서는 진실을 듣고,
//또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.
//지민이는 이런 일을 모두 피해야 한다.
vector<int> partyPeople[51];
for (int i = 0; i < m; i++)
{
int tmp;
cin >> tmp;
bool flag = false;
for (int j = 0; j < tmp; j++)
{
int num;
cin >> num;
if (isKnow[num]) {
flag = true;
partyPeople[i].insert(partyPeople[i].begin(), num);
}
else partyPeople[i].push_back(num);
}
if (flag) {
for (int j = 1; j < tmp; j++) {
union_find(partyPeople[i][0], partyPeople[i][j]);
isKnow[partyPeople[i][j]] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 1; j < partyPeople[i].size(); j++) {
union_find(partyPeople[i][0], partyPeople[i][j]);
}
}
//truth인 사람들과 같은 그룹에 속해있으면 모두 true
for (int i = 1; i <=n; i++) {
if (isKnow[i]) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (isSame(i, j)) {
isKnow[j] = true;
}
}
}
}
int cnt = m;
for (int i = 0; i < m; i++) {
bool flag = false;
for (int j = 0; j < partyPeople[i].size(); j++) {
if (isKnow[partyPeople[i][j]]) {
flag= true;
break;
}
}
if (flag) cnt--;
}
cout << cnt << '\n';
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|