[자료구조] 백준 1043번: 거짓말 (C++)

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

1043번: 거짓말

진실을 아는 사람들을 모두 같은 집합에 넣어주고, 쿼리 중에서도 진실을 모르는 사람이지만 진실을 아는 사람과 같이 있을 경우

진실을 아는 사람들의 집합에 넣어준다.

 

그리고, 다시 쿼리를 순회하면서(다시 쿼리를 순회하기 위해 쿼리를 담아두어야 함)

어떠한 노드가 진실을 아는 사람들의 집합에 속하기라도 한다면 바로 과장되어서 말하지 못하게 처리한다.

 

과정마다 getRoot(node)를 쓸 것인지, parent[node]를 쓸 것인지 고민하게 했던 문제다.

 

[AC 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, k;
vector<int> truth;
vector<int> query[50];
int parent[51];

int gR(int node){
    if(node == parent[node]) return node;
    else return parent[node] = gR(parent[node]);
}

void unionNodes(int a, int b){
    int rA = gR(a);
    int rB = gR(b);
    
    if(rA < rB){
        parent[rB] = rA;
    }
    else{
        parent[rA] = rB;
    }
}

int main(){
    cin >> n >> m >> k;
    
    if(k == 0){
        cout << m;
        return 0;
    }
    
    // parent 초기화
    for(int i = 1; i <= n; i++){
        parent[i] = i;
    }
    
    for(int i = 0; i < k; i++){
        int person;
        cin >> person;
        truth.push_back(person);
    }
    
    // getRoot했을 때 혹시 모를 제일 작은 값이 반환되지 않을까
    // 싶어서 정렬
    sort(truth.begin(), truth.end());
    
    // truth끼리 같은 집합에 묶기
    for(int i = 1; i < truth.size(); i++){
        unionNodes(truth[0], truth[i]);
    }
    
    // 쿼리 입력
    for(int i = 0; i < m; i++){
        int num;
        cin >> num;
        for(int j = 0; j < num; j++){
            int node;
            cin >> node;
            query[i].push_back(node);
        }
    }
    
    // 각 쿼리마다 같은 집합에 묶기
    // 이 과정에서 진실을 모는 사람이 진실을 아는 사람과
    // 있을 경우에 진실을 아는 사람의 집합으로 들어간다
    for(int i = 0; i < m; i++){
        if(query[i].size() < 2) continue;
        for(int j = 1; j < query[i].size(); j++){
            unionNodes(query[i][j], query[i][j - 1]);
        }
    }
    
    int result = 0;
    int knowTruth = gR(truth[0]);
    
    for(int i = 0; i < m; i++){
        bool check = 0;
        for(int j = 0; j < query[i].size(); j++){
            if(gR(query[i][j]) == knowTruth){
                check = 1;
                break;
            }
        }
        
        if(check == 0) result++;
    }
    cout << result;
    return 0;
}