[BOJ/백준][Gold4] 1403 : 거짓말(C++)

www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

[난이도] Gold4

[유형] DFS

 

[풀이]

지민이는 진실을 아는 사람이 있는 파티에서는 거짓말을 못한다. 어떤 파티에서 진실을 아는 사람이 있어서 진실을 말하면 그 파티에 참여한 진실을 모르는 사람이 참여한 모든 파티에서도 거짓말을 할 수 없다. 즉, 지민이가 진실을 말한 파티에 있는 모든 사람들은 진실을 아는거나 마찬가지이다. 이 성질을 이용하여 진실을 아는 사람들을 DFS를 이용하여 갱신해주면 답을 구할 수 있다.

 

#include <cstdio>
#include <vector>
using namespace std;
int N,M;
vector<int> pp[51],pty[51],tp;
bool visit[51];
void dfs(int n){
    visit[n] = 1;
    for(auto ptn : pp[n]){
        for(auto p : pty[ptn]){
            if(!visit[p]) dfs(p);
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    int t,v;
    scanf("%d",&t);
    for(int i=0;i<t;i++) {
        scanf("%d",&v);
        tp.push_back(v);
    }
    for(int i=1;i<=M;i++){
        scanf("%d",&t);
        for(int j=0;j<t;j++){
            scanf("%d",&v);
            pty[i].push_back(v);
            pp[v].push_back(i);
        }
    }

    for(auto a : tp) dfs(a);
    int ans = 0;
    for(int i=1;i<=M;i++){
        bool ok = 1;
        for(auto p : pty[i]) {
            if(visit[p]){
                ok = 0;
                break;
            }
        }
        if(ok) ans++;
    }
    printf("%d",ans);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1043.cpp