[백준 1043] 거짓말 (C++)

1043번: 거짓말

 

재미있는 문제였다.

나는 사람과 파티를 똑같이 하나의 정점으로 보았다. 둘다 최대 50이므로 사람은 51부터, 방은 1부터 번호를 가지도록 설정했다.

 

진실 감별사부터 시작하는 dfs를 수행한다. 이때 연결되는 모든 정점은 진실 감별사로 바뀌게 된다.

 

처음 주어진 진실 감별사와 연결된 모든 정점을 진실 감별사로 바꾸고, 아직까지 진실 감별사가 되지 않은 사람의 수를 출력하면 답을 구할 수 있다.

 

처음에 Union find로 풀려고 했다가 너무 어려워졌다. 그래프를 계속 그려보면서 생각하니 dfs로 서로간의 연결만 생각해주면 되는 문제였어서 다행히 풀 수 있었다.

 

#include <iostream>
#include <vector>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
int N, M;
vector<int> party[101];
vector<int> truemanlist;
bool trueman[101];
bool visited[101];
 
void input(){
    cin >> N >> M;
    int a, b;
    cin >> a;
    for(int i = 0; i < a; i++){
        cin >> b;
        truemanlist.push_back(b+50);
        trueman[b+50] = 1;
    }
    
    for(int i = 0; i < M; i++){
        cin >> a;
        for(int j = 0; j < a; j++){
            cin >> b;
            party[i].push_back(b + 50);
            party[b+50].push_back(i);
        }
    }
}
 
void dfs(int now){
    trueman[now] = true;
    visited[now] = true;
    
    for(int i = 0; i < party[now].size(); i++){
        int next = party[now][i];
        if(visited[next]) continue;
        dfs(next);
    }
}
 
void solve(){
    for(int i = 0; i < truemanlist.size(); i++){
        int now = truemanlist[i];
        dfs(now);
    }
    
    int ans = 0;
    for(int i = 0; i < M; i++){
        if(!trueman[i]) ans++;
    }
    
    cout << ans << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}