BOJ 1043 거짓말

📝 문제 정보

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

🧐 관찰 및 접근

지민이는 모든 파티에 참여해야하므로, 진실을 아는 사람이 있는 파티의 모든 사람은 진실을 알게 된다.
- 모든 파티에 대해 진실을 알게 된 사람을 확인한 후, 진실을 아는사람이 없는 파티들의 수를 세면 된다.
- 유니온 파인드, 분리 집합으로 해결하자.

💻 풀이

코드 (C++):

void solve(){
    int N, M; cin >> N >> M;
    vector<vector<int>> parties;
    UnionFind UF(N+1); // 0은 진실을 아는 사람
    
    int cnt; cin >> cnt;
    rep(i, 0, cnt){
        int a; cin >> a;
        UF.merge(0, a);
    }

    rep(i, 0, M){
        cin >> cnt;
        vector<int> party(cnt);
        rep(j, 0, cnt) cin >> party[j];
        parties.push_back(party);
        rep(j, 0, cnt-1) UF.merge(party[j], party[j+1]);
    }
    
    int ans = 0;
    for(auto party: parties){
        bool flag = true;
        for(auto p: party) if(UF.find(p) == 0) flag = false;
        if(flag) ans++;
    }
    cout << ans;
}