BOJ - 거짓말(1043)

코드

#include<iostream>
#include<vector>
using namespace std;
int N, M;
vector<int> party[51];
int getRoot(vector<int> parent, int idx)
{
    if (parent[idx] == idx) return idx;
    else return getRoot(parent, parent[idx]);
}
 
bool find(vector<int> parent, int a, int b)
{
    a = getRoot(parent, a);
    b = getRoot(parent, b);
    if (a == b) return true;
    else return false;
}
 
void my_union(vector<int> &parent, int a, int b)
{
    a = getRoot(parent, a);
    b = getRoot(parent, b);
    parent[b] = a;
}
 
int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N >> M;
    vector<int> parent(N + 1);
    vector<int> knows;
    int know, people, num;
    for(int i=1; i<=N; i++)
        parent[i] = i;
    cin >> know;
    for(int i=0; i<know; i++)
    {
        cin >> num;
        knows.push_back(num);
    }
    for(int i=0; i<M; i++)
    {
        cin >> people;
        for(int j=0; j<people; j++)
        {
            cin >> num;
            party[i].push_back(num);
        }
    }
    for(int i=0; i<M; i++)
    {
        int v1 = party[i][0];
        for(int j=1; j<party[i].size(); j++)
        {
            int v2 = party[i][j];
            my_union(parent, v1, v2);
        }
    }
    int cnt = 0;
    for(int i=0; i<M; i++)
    {
        int flag = 0;
        for(int j=0; j<party[i].size(); j++)
        {
            if(flag)
                break;
            int person = party[i][j];
            for(int k=0; k<knows.size(); k++)
            {
                if (find(parent, person, knows[k]) == true)
                {
                    flag = 1;
                    break;
                }
            }
        }
        if (!flag)
            cnt++;
    }
    printf("%d\n", cnt);
    return (0);
}

우선 지민이의 소문을 아는 사람들을 knows 배열에다가 저장해놓고, 각 파티에 참여한 사람들에 대해서 모두 union을 해준다. 

그 후, 파티의 개수(M) 만큼 반복문을 돌면서 i번 째 파티에 참여한 사람 중 한명이라도 참여한 사람의 부모와 knows 배열에 있는 사람들의 부모가 같은 사람이 있을 경우 

=> find()의 결과 값이 true일 경우 그 파티에서 지민이는 거짓말을 할 수 없게 된다.