백준[1043] 거짓말

문제 설명

문제 링크

http://icpc.me/1043

1043번: 거짓말

풀이

유니온 파인드를 이용해서 풀 수 있다.

진실을 아는 사람들을 같은 집합에 넣어두고, 파티 구성원들을 같은 집합에 넣을 때, 만약 이 집합에 진실을 아는 사람들이 있다면 진실을 아는 사람 그룹에 그 파티 구성원들을 모두 넣어야 한다. 그 후에 파티 구성원들 집합을 확인하며 진실을 모르는 사람들만 모여있는 집합의 개수를 세면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int par[55];

int find(int x) { 
    if (x == par[x] || x == -1) return x;
    return par[x] = find(par[x]); 
}

int main() {
    ios::sync_with_stdio(0);
    vector<vector<int>> v;
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) par[i] = i;
    int k; cin >> k;
    while (k--) {
        int num; cin >> num;
        par[num] = -1;
    }
    while (m--) {
        int t; cin >> t;
        vector<int> tmp;
        while (t--) {
            int num; cin >> num;
            tmp.push_back(num);
        }
        v.push_back(tmp);
    }
    for (auto &arr : v) {
        for (int i = 0; i < arr.size() - 1; i++) {
            int x = find(arr[i]);
            int y = find(arr[i + 1]);
            if (x == y) continue;
            if (y == -1) swap(x, y);
            par[y] = x;
        }
    }
    int ret = 0;
    for (auto &arr : v) {
        if (~find(arr[0])) ret++;
    }
    cout << ret;
}