[백준 #1043 c++] 거짓말

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

1043번: 거짓말

 

방문하지 않은 정점을 탐색하는 그래프 이론을 알고 있다면 접근자체는 쉬운 문제다.

 

파티에 속한 사람들을 연결리스트로 나타낸 이중배열과

각 사람이 속한 파티를 연결리스트로 나타낸 이중배열을 만들었다.

 

굳이 각 사람에 대한 이중배열을 또 만든 이유는 어떤 사람이 어떤 파티에 있는지를 찾는 데에 필요한 시간을 줄이기 위해서이다.

 

진실을 알고 있는 사람부터 dfs로 탐색하여

그 사람이 속한 파티를 전체 파티에서 제외한다는 의미로 1을 빼주는 식으로 전개한다.

 

그리고 그 파티에서 또 사람들을 탐색하면서

아직 진실을 모르는 사람에 한해 또다시 dfs를 진행한다.

그리고 위 내용들을 반복한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int ans = 0;
bool truth[51];
bool visit[51];
vector<vector<int>> party;
vector<int> person[51];

void dfs(int p) {
    for (int i = 0; i < person[p].size(); i++) {
        if (visit[person[p][i]]) continue;
        visit[person[p][i]] = true;
        ans--;

        auto pty = party[person[p][i] - 1];
        for (int j = 0; j < pty.size(); j++) {
            if (!truth[pty[j]]) {
                truth[pty[j]] = true;
                dfs(pty[j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, t;
    cin >> n >> m >> t;
    ans = m;
    for (int i = 0; i < t; i++) {
        int p;
        cin >> p;
        truth[p] = true;
    }
    for (int i = 0; i < m; i++) {
        int p_n;
        cin >> p_n;
        vector<int> pList;
        for (int j = 0; j < p_n; j++) {
            int p;
            cin >> p;
            pList.push_back(p);
            person[p].push_back(i + 1);
        }
        party.push_back(pList);
    }

    for (int i = 1; i <= 50; i++) {
        if (truth[i]) {
            dfs(i);
        }
    }

    cout << ans;

    return 0;
}

 

Union Find로 푸는게 정석인거 같은데 코드가 길어지는게 싫어서 그냥 이렇게 풀었다.