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

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

1043번: 거짓말

---

거짓말 문제는 그래프를 이용하여 해결할 수 있습니다.

 

1. 파티에서 거짓말을 하려면 해당 파티에 오는 사람들은 모두 진실을 알지 못해야합니다.
2. 진실을 아는 사람이 존재하지 않는다면, 모든 파티에서 과장을 할 수 있습니다.
3. A는 진실을 아는 사람, B는 진실을 아는 사람과 같이 파티에 참석한 사람일 때, B가 참석한 파티에서도 거짓말을 할 수 없습니다. 
   
   1. 먼저, B와 파티에서 거짓말을 한 경우, A와의 파티에서 진실을 말해야하기 때문에 거짓말쟁이가 됩니다.
   2. 먼저, A와의 파티에서 진실을 말한 경우, B와의 파티에서 거짓말을 하면 거짓말쟁이가 됩니다. 

2 2
1 A
2 A B
2 B

이와 마찬가지로, B와 같이 파티에 참석한 사람이 참석한 파티에서도 거짓말을 할 수 없습니다. 

 

이를 이용하여, 진실을 아는 사람과 연결된 사람들이 참석한 모든 파티에서는 거짓말을 할 수 없습니다. 

 

아래는 전체 코드입니다. 

#include <bits/stdc++.h>
using namespace std;

int vis[51];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;    // 사람 수와 파티의 수 입력 받음
    int tn; cin >> tn; 

    vector<vector<int>> party(m);   // 각 파티에 참석하는 사람
    vector<vector<int>> linked(n + 1); 
    vector<int> t(tn); // 진실을 아는 사람들
    
    for(int i = 0; i < tn; i++) cin >> t[i];   // 진실을 아는 사람들 입력 받음

    for(int i = 0; i < m; i++){
        int c; cin >> c; 
        vector<int> participant(c); // i번째 파티에 참석하는 사람들

        for(int j = 0; j < c; j++) cin >> participant[j];   // i번째 파티에 참석하는 사람들 입력 받음
        party[i] = participant;
        
        for(int j = 0; j < c - 1; j++){ // 같은 파티에 참석한 사람들을 연결
            int u = participant[j], v = participant[j + 1]; 
            linked[u].push_back(v);
            linked[v].push_back(u);
        }
    }

    for(int i = 0; i < t.size(); i++){  // 진실을 아는 사람을 시작점으로 하여 BFS 수행
        int st = t[i];
        queue<int> q;
        q.push(st);
        vis[st] = 1;

        while(!q.empty()){
            int cur = q.front(); q.pop();
            for(auto nxt : linked[cur]){
                if(vis[nxt] != 0) continue;
                q.push(nxt);
                vis[nxt] = 1;
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < m; i++){
        bool avail = true;
        for(int j = 0; j < party[i].size(); j++){   // 파티에 참석한 인원들이 모두 진실을 아는 사람들과 관련이 없는 경우에만 거짓말을 할 수 있음
            if(vis[party[i][j]] != 0) avail = false;
        }
        if(avail) ans++;
    }

    cout << ans << "\n";
}