[백준] 거짓말(1043)

문제 링크 : [백준] 거짓말(1043)

문제 설명

N명의 사람이 M개의 파티에 참석하려고 합니다.
지민이는 각 파티에서 거짓말을 하고 싶은데, 진실을 아는 사람이 K명이 있습니다.
K명의 사람이 참석한 파티와 그 파티에 참석한 사람이 참석하는 다른 파티에서는 거짓말을 할 수 없습니다.
지민이는 최대 몇개의 파티에서 거짓말을 할 수 있는지 구하세요.

입력

N(사람 수, 1 <= N <= 50)
M(파티 수, 1 <= M <= 50)
K(진실을 아는 사람의 수, 1 <= 50)
KV_i(진실을 아는 사람이 K개 주어집니다.)
F_i(i번째 파티에 참석하는 사람의 수, 1 <= F_i <= 50)
FV_i(i번째 파티에 참석하는 사람)

4 3
0
2 1 2
1 3
3 2 3 4

출력

3

카테고리

#DisjointSet

시간 복잡도 상한

O(2ⁿ) 이하면 될 것 같습니다.

해결 방법

1. 진실을 아는 사람이 참석하는 파티에 참석하는 사람들을 모두 구해야 합니다.
2. 그 사람들이 참석하는 모든 파티에 참석하는 사람들을 또 모두 구해야합니다.
3. 이런 작업들을 단순화하려면 특정 사람과 같은 파티에 한번이라도 참석하는 사람, 그와 연쇄적으로 이어지는 모든 사람들을 같은 그룹으로 관리하면 됩니다.
4. 진실을 아는 사람과 같은 그룹으로 묶이는 사람이 있고, 그 사람들이 참석하는 파티는 거짓말을 할 수 없는 파티가 됩니다.
5. 3에서 그룹 관리는 DisjointSet을 이용하여 그룹을 관리합니다.
6. 각 파티별로 진실을 아는 사람과 같은 그룹에 포함되는 사람이 파티에 참석하는지를 파악하여 거짓말을 할 수 있는 파티의 수를 확인합니다.

시간복잡도

O(N * M)

코드

#include<cstdio>
#include<vector>
using namespace std;
int n,m,e[51],c,t,i,j,g[51][51];
vector<int>v;
int f(int a){
    if(e[a]==a)return a;
    return e[a]=f(e[a]);
}
void u(int a,int b){
    e[f(a)]=f(b);
}
int main(){
    for(n=1;n<51;n++)e[n]=n;
    scanf("%d%d",&n,&m);
    scanf("%d",&t);
    while(t--)scanf("%d",&c),v.push_back(c);
    for(i=0;i<m;i++){
        scanf("%d",g[i]);
        for(j=1;j<=g[i][0];j++){
            scanf("%d",g[i]+j);
            u(g[i][1],g[i][j]);
        }
    }
    for(c=i=0;i<m;i++){
        n=1;
        for(j=1;n&&j<=g[i][0];j++){
            for(t=0;n&&t<v.size();t++)if(f(g[i][j])==f(v[t]))n=0;
        }
        c+=n;
    }
    printf("%d",c);
}