백준 1043번 거짓말 (C++)

1043번: 거짓말

dsu를 활용한 문제이다. 크루스칼 알고리즘에서 활용된 find-union 방식을 활용하여 진실을 아는 사람이 포함된 파티들을 확인하였다. 각 파티의 첫번재 번호가 부모가 되고 이를 parent배열에 표시해주었다. 각 파티마다 반복문을 돌면서 진실을 아는 사람의 부모가 포함된 파티라면 해당 파티는 진실만을 말해야하기에 이를 카운트해주고 후에 전체 파티에서 이를 뺀 값을 출력해주었다.
생각보다 어려웠던 문제였다. dsu라는 개념을 잘 알아두자.

#include <iostream>
#include <vector>

using namespace std;

int N, M, p, res = 0;
vector<int> t;
vector<int> v[50];
int parent[50];

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

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

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

void solution() {
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < M; i++) {
        int a = v[i][0];
        for (int j = 0; j < v[i].size(); j++) {
            int b = v[i][j];
            unionParent(a, b);
        }
    }

    for (int i = 0; i < M; i++) {
        bool tf = false;
        for (int j = 0; j < v[i].size(); j++) {
            if (tf) break;
            int a = v[i][j];
            for (int k = 0; k < t.size(); k++) {
                int b = t[k];
                if (findParent(a) == findParent(b)) {
                    tf = true;
                    break;
                }
            }
        }

        if (tf) res++;
    }

    cout << M - res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    cin >> p;
    for (int i = 0; i < p; i++) {
        int a;
        cin >> a;
        t.push_back(a);
    }

    for (int i = 0; i < M; i++) {
        cin >> p;
        for (int j = 0; j < p; j++) {
            int a;
            cin >> a;
            v[i].push_back(a);
        }
    }

    solution();

    return 0;
}