문제 URL : https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
문제 접근법 :
union find를 이용한 알고리즘입니다.
진실을 아는자와 파티를 한다면 같은 집단으로 묶고 그 집합들도 진실을 알도록 해줍니다.
그리고 다시 파티에서 진실이 아는자들이 한명도 없다면 cnt값을 증가시키면 되기때문에 어렵지 않은 문제입니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> parent,fact;
vector<vector<int>> v;
int find(int idx) {
if (idx == parent[idx])return idx;
return parent[idx] = find(parent[idx]);
}
void Union(int a, int b) {
a = find(a);
b = find(b);
parent[b] = a;
if (fact[a] || fact[b])
{
fact[a] = fact[b] = true;
}
}
void input() {
cin >> n >> m;
parent.resize(n + 1);
fact.resize(n + 1);
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int num;
cin >> num;
fact[num] = 1;
}
for (int i = 0; i < m; i++) {
cin >> k;
vector<int> v2(k);
for (int j = 0; j < k; j++) {
cin >> v2[j];
}
v.push_back(v2);
}
}
void solve() {
int res = 0;
for (int i = 1; i <= n; i++)
parent[i] = i;
for (int i = 0; i < m; i++)
{
for (int j = 1; j < v[i].size(); j++) {
Union(v[i][j - 1], v[i][j]);
}
}
for (int i = 0; i < m; i++)
{
int flag = 1;
for (int j = 0; j < v[i].size(); j++) {
if (fact[find(v[i][j])])
{
flag = false;
break;
}
}
res += flag;
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이라도 대글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 13900 순서쌍의 곱의 합 (0) | 2021.08.16 |
|---|---|
| 백준 1024 수열의합 (0) | 2021.08.15 |
| 백준 20058 마법사 상어와 파이어스톰 (0) | 2021.08.13 |
| 백준 19238 스타트 택시 (0) | 2021.08.11 |
| 백준 1948 임계경로 (0) | 2021.08.04 |
