[ 백준 1043 ] 거짓말 (c/c++)

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

 

 

[ 문제 요약 ]

사람의 수 N과 파티의 수 M와 진실을 아는 사람의 수와 번호, 각 파티에 오는 사람들의 번호가 주어질 때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 출력한다.

 

 

[ 문제 풀이 ]

1. 각 파티에 있는 사람들끼리 Union 그룹을 만든다.

2. 한 파티에 오는 사람들 중에 진실을 아는 사람이 있다는 지 Union Find를 통해 확인한다.

 

 

[ 소스 코드 ]

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

int N, M, ans;
int P[55];
vector<int> people[55];
vector<int> tp;

void Init(int n){
    ans = M;
    for (int i=1; i<=n; i++) P[i] = i;
}

int Find(int v) {
    if (v == P[v]) return v;
    return P[v] = Find(P[v]);
}

void Union(int u, int v) {
    u = Find(u); v = Find(v);
    if (u != v) P[u] = v;
}

bool isUnion(int u, int v) {
    u = Find(u); v = Find(v);
    if (u != v) return false;
    return true;
}

int main() {
    int a, b;
    cin >> N >> M;
    cin >> a;
    for (int i=0; i<a; i++){
        cin >> b;
        tp.push_back(b);
    }
    
    for (int i=0; i<M; i++){
        cin >> a;
        for (int j=0; j<a; j++){
            cin >> b; 
            people[i].push_back(b);
        }
    }
    
    Init(N);

    for (int i=0; i<M; i++)
        for (int j=1; j<people[i].size(); j++){
            a = people[i][0]; b = people[i][j];
            Union(a, b);
        }

    for (int i = 0; i < M; i++) {
        bool check = true;
        for (int j = 0; j < people[i].size(); j++) {
            a = people[i][j];
            for (int k = 0; k < tp.size(); k++) {
                b = tp[k];
                if (isUnion(a, b)) {
                    check = false;
                    break;
                }
            }
        }
        if (!check) ans--;
    }

    cout << ans;
    
    return 0;
}

 

 

 

[ 주의할 점 ]

Union Find를 써야 하는 문제인데, Union Find를 써야하는 것을 떠올리기 어려운 문제였다.