그래프/유니온 파인드

거짓말

4gats 2023. 9. 2. 14:46

https://www.acmicpc.net/problem/1043

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

 

당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고,

또다른 파티에서는 과장된 이야기를 들었을 때도

지민이는 거짓말쟁이로 알려지게 된다. 

 

이 구절이 유니온 파인드를 쓰게 만든다!

파티를 모두 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> parent;
vector<int> trueP;
vector<vector<int>> party;
int result;
 
int find(int a)
{
    if (a == parent[a])
        return a;
    else
        // 재귀 함수로 구현
        // 재귀를 탈출하면서 parent의 값이 바뀐다.
        return parent[a] = find(parent[a]);
}
 
void unionfunc(int a, int b)
{
    a = find(a);
    b = find(b);
 
    if (a != b)
        parent[b] = a;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m, t;
    cin >> n >> m >> t;
    trueP.resize(t);
 
    for (int i = 0; i < t; i++)
    {
        cin >> trueP[i];
    }
 
    party.resize(m);
    for (int i = 0; i < m; i++)
    {
        int party_size;
        cin >> party_size;
 
        for (int j = 0; j < party_size; j++)
        {
            int tmp;
            cin >> tmp;
            party[i].push_back(tmp);
        }
    }
    parent.resize(n + 1);
    
    for (int i = 0; i <= n; i++)
    {
        parent[i] = i;
    }
 
 
    for (int i = 0; i < m; i++)
    {
        int firstpeople = party[i][0];
        for (int j = 1; j < party[i].size(); j++)
        {
            unionfunc(firstpeople, party[i][j]);
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        bool isPossible = true;
        int cur = party[i][0];
        for (int j = 0; j < t; j++)
        {
            if (find(cur) == find(trueP[j]))
            {
                isPossible = false;
                break;
            }
        }
        if (isPossible) {
            result++;
        }
    }
 
    cout << result;
    return 0;
}
 cs