[백준] 1043.cpp : 거짓말

www.acmicpc.net/problem/1043

1043번: 거짓말

---

• 진실을 알고 있는 사람이 속한 파티의 참가자들은 모두 진실을 알게 된다.
• 그 참가자들이 속한 다른 파티 역시 모두 진실을 알게 된다.
• 파티의 참가자들을 하나의 그룹으로 묶는다.
• 사람을 기준으로 그룹을 묶게 되면, 다른 파티와 중복된 참가자가 있으면 모두 같은 그룹으로 묶이게 된다.
• 모든 그룹을 나눈 뒤, 처음에 입력해준 진실을 아는 사람들의 그룹과 파티의 멤버들을 전부 비교해나가면, 해당 파티가 진실을 아는 사람들의 그룹인지 알 수 있다.
• 말로만 설명하기가 조금 까다로운데, 유니온 파인드를 찾아보면 더 명확하게 이해할 수 있다.

---

#include <iostream>
#include <vector>

using namespace std;

int n, m, ans;
vector<int> know;               // 입력으로 주어진, 기존에 알고있던 사람들
vector<vector<int>> party;      // 각 파티에 참여하는 사람들
int parent[51];                 // 모든 사람들을 그룹화시키는 배열
int num, temp;

int find(int idx)               // 해당 사람의 최종 그룹을 반환 (루트 노드)
{
    if(idx != parent[idx]) idx = find(parent[idx]); // 루트노드가 아닐 시 해당 노드의 부모 노드로 재귀 호출
    return idx;
}

void union_(int x, int y)       // 두 사람을 그룹화시킴 (루트 노드를 같게 만듦)
{
    x = find(x);
    y = find(y);
    parent[y] = x;
}

int main(void)
{
    cin >> n >> m;
    cin >> num;

    for(int i = 0 ; i < num ; i++)
    {
        cin >> temp;
        know.push_back(temp);
    }
    for(int i = 1 ; i <= n ; i++) parent[i] =i;

    for(int i = 0 ; i < m ; i++)                    // 모든 파티들에 대해서 서로 연결시키는 과정
    {
        cin >> temp;
        vector<int> member;
        cin >> num;
        member.push_back(num);
        int prev;
        for(int k = 1 ; k < temp ; k++)             // 각 파티의 멤버들을 같은 그룹으로 묶어놓음
        {
            prev = num;
            cin >> num;
            union_(prev, num);                      // 묶는 과정에서 다른 파티원과도 연결될 수 있음
            member.push_back(num);
        }
        party.push_back(member);
    }
    for(int i = 0 ; i < know.size() ; i++)
    {
        know[i] = find(know[i]);
    }

    for(int i = 0 ; i < m ; i++)                    // 모든 파티들을 돌면서
    {
        bool able = true;
        for(int j = 0 ; j < party[i].size() ; j++)  // 각 파티의 멤버들 중
        {
            int root = find(party[i][j]);
            for(int k = 0 ; k < know.size() ; k++)
            {
                if(root == know[k])                 // 한명이라도 진실을 알고있는 사람과 같은 그룹에 있다면
                {
                    able = false;                   // 해당 파티를 세지 않음
                    break;
                }
            }
            if(able == false) break;
        }
        if(able) ans++;                             // 해당 파티에 아무도 진실을 아는 그룹과 엮여있지 않을 때에만 카운트
    }
    cout << ans << endl;
}