백준 7511번: 소셜 네트워킹 어플리케이션 (C++)

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

7511번: 소셜 네트워킹 어플리케이션

---

Solved By: Union-Find

#include <iostream>
#define MAX 1000000
using namespace std;

int T;
int parent[MAX];

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

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

bool find(int a, int b){
    int rA = getRoot(a);
    int rB = getRoot(b);
    
    if(rA == rB) return true;
    else return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> T;
    for(int t = 1; t <= T; t++){
        int n, k;
        cin >> n;
        cin >> k;
        
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
        
        for(int i = 0; i < k; i++){
            int a, b; cin >> a >> b;
            unionNodes(a, b);
        }
        
        int m; cin >> m;
        
        cout << "Scenario " << t << ':' << '\n';
        for(int i = 0; i < m; i++){
            int a, b; cin >> a >> b;
            if(find(a, b)) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        
        cout << '\n';
    }
    
    return 0;
}