백준 4195 친구 네트워크

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

4195번: 친구 네트워크

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

map<string, string> parent;
map<string, int> cnt;

string findParent(string k){
    return parent[k] == k ? k : parent[k]=findParent(parent[k]);
}


void uni(string a, string b){

    string fa = findParent(a);
    string fb = findParent(b);

    if (fa == fb) {
        return;
    } else {

        parent[fb] = fa;
        cnt[fa] += cnt[fb];
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int t;
    cin >> t;

    for (int test = 0; test < t; test++) {

        int f;
        cin >> f;

        cnt.clear();
        parent.clear();



        //friend는 c++의 예약어: 변수 선언 시 주의
        for (int fre = 0; fre < f; fre++) {



            string a, b;

            cin >> a >> b;

            //네트워크에 해당 친구가 처음 참여했을 경우 추가
            if (cnt.count(a) == 0) {
                cnt.insert(make_pair(a, 1));
                parent.insert(make_pair(a, a));
            }
            if (cnt.count(b) == 0) {
                cnt.insert(make_pair(b, 1));
                parent.insert(make_pair(b, b));
            }

            uni(a, b);


            cout << cnt[findParent(a)] << "\n";


        }

    }

    return 0;
}

 

disjoint set 문제이지만 정수 대신 string으로 구하는 문제이다.

map으로 <친구 이름, 네트워크의 수>, <친구 이름, 부모 이름>을 선언하고, 

해당 친구가 처음 들어왔다면 두 맵에 추가를 한다. 이후 같은 친구 네트워크에 union 연산을 하고 해당 친구 네트워크의 수를 출력하면 정답을 출력할 수 있다.

 

 * friend는 c++의 예약어 중 하나이다. 변수 선언 시 주의하자