[BOJ/C++] 1043 거짓말

유니온 파인드를 이용해 문제를 해결할 수 있습니다.

각 파티에 진실을 알고있는 사람과 연결되어 있다면 해당 파티에서는 과장된 얘기를 할 수 없습니다.

1. 각 파티의 사람들을 union 연산을 통해 같은 그룹으로 만듭니다
2. 각 파티의 임의의 사람과 진실을 알고있는 사람을 비교해 한 명이라도 같은 그룹에 속해있다면 해당 파티에서는 과장된 얘기를 할 수 없습니다.
3. 한 명이라도 같은 그룹에 속해있지 않다면 결과값을 증가시킵니다.
4. 위의 과정을 모든 파티에 대해 진행합니다

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<int> parent;
static vector<int> truePerson;
static vector<vector<int>> party;
void Union(int a, int b);
int Find(int a);


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M, T;
    int result = 0;
    cin >> N >> M >> T;

    parent.resize(N + 1);
    truePerson.resize(T);
    party.resize(M);

    for (int i = 0; i < T; i++)
        cin >> truePerson[i];

    for(int i=0; i<M; i++)
    {
        int partySize;
        cin >> partySize;

        for(int j=0; j<partySize; j++)
        {
            int temp;
            cin >> temp;
            party[i].push_back(temp);
        }
    }

    for (int i = 0; i <= N; i++)
        parent[i] = i;

    for(int i=0; i<M; i++)
    {
        int first = party[i][0];
        for (int j = 1; j < party[i].size(); j++)
            Union(first, party[i][j]);
    }

    for(int i=0; i<M; i++)
    {
        bool isPossible = true;
        int cur = party[i][0];
        for(int j=0; j<T; j++)
        {
	        if(Find(cur)==Find(truePerson[j]))
	        {
                isPossible = false;
                break;
	        }
        }
        if (isPossible)
            result++;
    }
    cout << result;

    return 0;
}


void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);

    if (a != b)
        parent[b] = a;
}

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