[BOJ] 1043번 : 거짓말(C++)

문제 링크 : 백준 1043번

[문제 접근]

진실을 아는 사람과 같은 파티면 참가할 수 없게 만들어야하므로 Union-Find로 접근했다.

1. 같은 파티에 있는 사람들을 Union해준다.
2. 파티에 참가하는 사람들을 탐색하며 진실을 아는 사람들과 Find로 비교해서 같으면 진실을 아는 사람과 같은 파티이므로 그 파티는 참여할 수 없다.

[소스 코드]

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

using namespace std;

int n, m;
int parent[51];
vector<int> arr[51];
vector<int> people;

int Find(int node) {
    if(parent[node] == node) return node;
    return parent[node] = Find(parent[node]);
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1 ; i<=n ; i++) {
        parent[i] = i;
    }
    int num;
    cin >> num;
    for(int i=0 ; i<num ; i++) {
        int a;
        cin >> a;
        people.push_back(a);
    }
    for(int i=0 ; i<m ; i++) {
        int a;
        cin >> a;
        int s, e;
        for(int j=0 ; j<a ; j++) {
            cin >> e;
            arr[i].push_back(e);
            if(j==0) {
                s = e;
                continue;
            }
            Union(s, e);
            s = e;
        }
    }
    int ans=0;
    if(num == 0) {
        cout << m;
    } else {
        for(int i=0 ; i<m ; i++) {
            bool check = true;
            for(int j=0; j<arr[i].size() ; j++) {
                int now = arr[i][j];
                for(int k=0; k<people.size() ; k++) {
                    if(Find(now) == Find(people[k])) { // 진실을 아는 사람
                        check = false;
                        break;
                    }
                }
                if(!check) break;
            }
            if(check) ans++;
        }
        cout << ans;
    }
    

    return 0;
}