[백준] 1043 - 거짓말

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

1043번: 거짓말

이 문제의 요점은 같은 파티에 한 번이라도 속한 사람은 전부 통한다는 것이다. 예를 들어 1번이 진실을 알고 있고 2번이 한번이라도 1번과 같은 파티에 참석했으면 순서에 상관없이 다른 파티에서는 2번은 진실을 아는 사람처럼 행동하게 된다. 그렇기에 이 문제는 한 번이라도 같은 파티에 참석해봤냐 안 해봤냐 나누는 문제로 Union-Find 알고리즘을 사용하면 된다.

 

더 자세히 말하자면 각 파티당 참여하는 인원을 다 Union 해준다. 그렇게하면 한 번이라도 파티에서 만난 적 있는 사람들로만 이루어진 그룹으로 나뉘어지게 된다. 그리고 각 파티당 참여인원을 loop 돌려 known(진실을 아는 사람)과 비교해주고 같은 그룹이면 답에서 뺀다. 그렇지 않으면 같은 파티에 한 번도 만나지 않기에 거짓말을 해도 된다.

#include <iostream>
#include <vector>
#define MAX 51
using namespace std;

vector<int> party[MAX], known;
int par[MAX];
int n, m, tmp, num, ans;

int Find(int a) {
    if (a == par[a]) return a;
    return par[a] = Find(par[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    par[b] = a;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> tmp;
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 0; i < tmp; i++) {
        cin >> num;
        known.push_back(num);
    }

    for (int i = 0; i < m; i++) {
        cin >> num;
        for (int j = 0; j < num; j++) {
            cin >> tmp;
            party[i].push_back(tmp);
            Union(party[i][0], party[i][j]);
        }
    }

    ans = m;

    for (int i = 0; i < m; i++) {
        bool flag = false;

        for (int j : party[i]) {
            if (flag) break;

            for (int k : known) {
                if (Find(j) == Find(k)) {
                    flag = true;
                    break;
                }
            }
        }

        if (flag) ans--;
    }

    cout << ans << "\n";
    return 0;
}