[유니온-파인드] 예제 문제: 거짓말_백준

예제 문제: 거짓말_백준

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

---

이전 풀이 => O(N^3*LogN)

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

int solution(vector<int> *party, vector<int> knower, int m){
    int totalCount = 0;

    set<int> knowerSet;
    for(int i=0; i<knower.size(); i++){
        knowerSet.insert(knower[i]);
    }

    // knower이 속한 파티에서 추가 knower 구하기    // O(n^3*logN)
    for(int over=0; over<m; over++){
        for(int i=0; i<m; i++){
            vector<int> party_one = party[i];
            bool flag = false;
            for(int j=0; j<party_one.size(); j++){
                int party_one_peple = party_one[j];
                if(knowerSet.find(party_one_peple) != knowerSet.end()){ // 진실을 아는 사람이 있다면
                    flag = true;
                    break;
                }
            }
            if(flag){   // 해당 파티에 진실을 아는 사람이 존재한다면
                for(int j=0; j<party_one.size(); j++){
                    int party_one_peple = party_one[j];
                    if(knowerSet.find(party_one_peple) == knowerSet.end())
                        knowerSet.insert(party_one_peple);
                }
            }
        }
    }

    // 다시 순회를 하며 파티 수 찾기
    for(int i=0; i<m; i++){
        vector<int> party_one = party[i];
        bool flag = false;

        for(int j=0; j<party_one.size(); j++){
            int party_one_people = party_one[j];
            if(knowerSet.find(party_one_people) != knowerSet.end()){
                flag = true;
                break;
            }
        }
        if(!flag)
            totalCount++;
    }

    return totalCount;
}

int main(){
    int n, m;   // 자연수
    cin >> n >> m;

    int k;      // 0 ~
    cin >> k;
    vector<int> knower;
    for(int i=0; i<k; i++){
        int x;
        cin >> x;
        knower.push_back(x); 
    }

    vector<int> party[m];
    for(int i=0; i<m; i++){
        int num = 0;
        cin >> num;
        for(int j=0; j <num; j++){
            int x;
            cin >> x;
            party[i].push_back(x);
        }
    }

    int result = solution(party, knower, m);
    cout << result << '\n';
}

---

유니온 파인드 풀이법

reference: https://yabmoons.tistory.com/463

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

// parent 찾기
int find_parent(int a, int *parent){
    if(a == parent[a])  
        return a;
    else    
        return parent[a] = find_parent(parent[a]);
}

// parent가 일치하는 지 => 즉 같은 집합에 속하는 지 체크
bool check_same_parent(int a, int b, int *parent){
    if(find_parent(a, parent) == find_parent(b, parent))
        return true;    // 같은 집합
    else
        return false;
}

// 유니온 파인드 풀이법
int solution(vector<int> *party, vector<int> knower, int n, int m){
    int totalCount = 0;

    // parent 배열 채우기
    int parent[n+1];
    for(int i=0; i<=n; i++){
        parent[i] = i;
    }

    
    for(int i=0; i<m; i++){
        // 같은 파티 그룹   
        int p1 = party[i][0];
        for(int j=1; j<party[i].size(); j++){
            int p2 = party[i][j];

            // Union (합집합으로 묶기?)
            p1 = find_parent(p1, parent);
            p2 = find_parent(p2, parent);
            parent[p2] = p1;
        }
    }

    // 다시 각 파티 순휘
    for(int i=0; i<m; i++){
        
        vector<int> party_one = party[i];
        // 하나의 파티 내부
        bool flag = false;
        for(int j=0; j<party_one.size(); j++){
            int p1 = party_one[j];
            // 한 사람에 대해 진실을 아는지 체크
            for(int k=0; k<knower.size(); k++){
                // IF 진실을 아는 사람
                if(check_same_parent(p1, knower[k], parent)) {  // 해당 파티에 진실을 아는 사람 존재
                    flag = true;				// 즉 같은 집합(같은 부모를 가짐)이라면 해당 파티는 포함시킬 수 없음(과장할 수 없음) 
                    break;
                }
                // ELSE
                    // 다시 knower 배열 순회
            }
            if(flag)
                break;
        }
        if(!flag)
            totalCount++;
    }

    return totalCount;

}

int main(){
    int n, m;   // 자연수
    cin >> n >> m;

    int k;      // 0 ~
    cin >> k;
    vector<int> knower;
    for(int i=0; i<k; i++){
        int x;
        cin >> x;
        knower.push_back(x); 
    }

    vector<int> party[m];
    for(int i=0; i<m; i++){
        int num = 0;
        cin >> num;
        for(int j=0; j <num; j++){
            int x;
            cin >> x;
            party[i].push_back(x);
        }
    }

    int result = solution(party, knower, n, m);
    cout << result << '\n';
}