[ BOJ 백준 4195번 - 친구 네트워크 ] 해설 및 코드

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

 

목적

두 사람의 친구 네트워크에 몇 명이 있는지 구하자.

 

접근법

1. 분리집합 자료구조로 친구 관계를 나타내보자. disjoint-set을 구현해 봤다면 어렵지 않은 문제이다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int p[(int)1e5 + 1];
 
int find(int i) {
    return (p[i] < 0 ? i : p[i] = find(p[i]));
}
 
int merge(int i, int j) {
    i = find(i), j = find(j);
    if (i == j)return -p[i];
    p[i] += p[j];
    p[j] = i;
    return -p[i];
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        unordered_map<string, int> m;
        memset(p, -1, sizeof(p));
        int idx = 0;
        int n; cin >> n;
        while (n--) {
            string a, b; cin >> a >> b;
            int& i = m[a], & j = m[b];
            if (i == 0)i = ++idx;
            if (j == 0)j = ++idx;
            cout << merge(i, j) << '\n';
        }
    }
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.