문제

1043번: 거짓말

풀이

진실을 알고 있는 사람들이 없는 파티의 개수를 세는 문제다.
진실을 알고 있는 사람들을 하나의 그룹으로 묶었다. 이를 위해 Uinon Find 알고리즘을 활용했다.
문제의 두번째 줄 입력으로 들어오는 사람들을 하나로 묶어 초기 그룹으로 만들었다. 그 그룹의 root는 0으로하여 구별하도록 한다.

같은 파티에 진실을 아는 사람이 있다면 그 파티의 모든 사람도 진실을 알게 되므로 같은 파티에 간 사람들도 같은 그룹으로 만든다. 만약 같은 그룹에 root가 0인 사람이 있다면 그 그룹 또한 모두 진실을 알고 있는 그룹에 속하게 된다.

하지만 문제 입력 순서 차이로
A 파티에 진실을 아는 사람이 없었는데, A 파티의 한 사람이 다른B파티에 진실을 아는 사람과 같이 B파티에 간다면 그 사람은 진실을 아는 사람이 되고 자동으로 그 사람이 전에 갔던 A파티의 사람들도 진실을 아는 사람 그룹에 속하게 된다. 이때문에 Union Find 알고리즘을 사용하였다.

마지막 거짓말을 해도 되는 파티인지 확인하기 위해
파티에 참가한 사람들의 그룹을 확인해서 root가 0인지 아닌지 확인 후 한 사람이라도 root가 0이라면 거짓말을 못하는 파티이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> root;
vector<vector<int>> partys;

int findSet(int x){
    if (root[x] == x){
        return x;
    }
    else{
        return root[x] = findSet(root[x]);
    }
}

void unionSet(int x, int y){
    int nx, ny;
    nx = findSet(x);
    ny = findSet(y);

    if (nx == ny) return;

    if (nx == 0 || ny == 0){
        root[nx] = 0;
        root[ny] = 0;
    }
    else {
        root[nx] = ny;
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
        
    // 1번째 줄 입력
    cin >> n >> m;
    root.assign(n+1, 0);
    partys.assign(m, vector<int>(0));
    for (int i=0; i<n+1; i++){
        root[i] = i;
    }

    // 2번째 줄 입력
    int repeat;
    cin >> repeat;
    for (int i=0; i<repeat; i++){
        int temp;
        cin >> temp;
        root[temp] = 0; // 0에 대한 find 와 uinon에서의 예외처리를 확실히 해야한다.
    }

    // 3번째 줄 부터 입력
    for (int i=0; i<m; i++){
        int temp;
        cin >> temp;
        partys[i].assign(temp, 0);
        for (int j=0; j<temp; j++){
            cin >> partys[i][j];
        }
        for (int j=0; j<temp-1; j++){
            unionSet(partys[i][j], partys[i][j+1]);
        }
    }
    
    int answer = m;
    for (int i=0; i<m; i++){
        for (int j=0; j<partys[i].size(); j++){
            if (findSet(partys[i][j]) == 0){
                answer -= 1;
                break;
            }
        }
    }
    cout << answer << endl;

    return 0;
}