거짓말
문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다.
파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다.
지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다.
당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다.
하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다.
따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다.
당연히, 어떤 사람이 진실을 듣고, 또 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.
지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다.
그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다.
이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다.
진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다.
사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수,
각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
유니온 파인드를 공부하면서 풀어본 문제이다.
우선 0번을 진실을 아는 사람 그래프라고 생각하고, 묶어줬다.
그 다음 파티를 입력 받고, 진실을 아는 사람이 들어있는 파티면 union을 해준다.
그런 뒤 다시 맨 처음부터 조사를 해야한다.
진실을 아는 사람이 있는 파티의 전원이 union되기 때문이다.
이 과정을 반복하면 정답을 출력할 수 있다.
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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cin >> n >> m; //사람, 파티
vector<int> parent(n+1);
vector<int> high(n+1, 1);
for(int i=0;i<=n;i++){
parent[i]=i;
}
function <int(int)> find = [&](int n){
if(n==parent[n])return n;
return parent[n] = find(parent[n]);
};
function <void(int, int)> uni = [&](int a, int b){
int u = find(a);
int v = find(b);
if(u==v)return;
if(high[u]>high[v]){
swap(u,v);
}
parent[u] = v;
if(high[u]==high[v])high[v]++;
};
cin >> a;
for(int i=0;i<a;i++){ //진실을 아는 사람
cin >> t;
uni(0, t);
}
vector<vector<int>> party(m);
vector<bool> check(m, 0);
for(int i=0;i<m;i++){
cin >> a;
for(int j=0;j<a;j++){
cin >> t;
party[i].push_back(t);
}
}
for(int i=0;i<m;i++){
for(int j=0;j<party[i].size();j++){
if(check[i]==0 && find(0)==find(party[i][j])){
check[i]=1;
for(int k=0;k<party[i].size();k++)uni(0,party[i][k]);
i=-1;
break;
}
}
}
int total=0;
for(int i=0;i<m;i++){
if(check[i]==0)total++;
}
cout << total;
return 0;
}