문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

  • 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

예제

예제 입력
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

예제 출력
2
3
4
2
2
4

접근

  • Disjoint-Set(Union-Find)를 공부하기 위해 찾은 문제다 보니 자연스럽게 이 방법으로 접근하게 되었다.
  • 이전에 풀었던 집합의표현과 같은 경우 같은 집합에 속하는지 아닌지만 알면 됐지만 이 경우 총 몇 명의 친구가 있는지 알아야 하며 이름은 고유하다는 특성을 생각하여 map을 활용했다.

내가 생각한 풀이

  • 이름과 부모를 저장하는 map, 이름과 친구 수를 저장하는 map을 선언한 후 Union-Find를 활용했다. 탐색의 효율성을 위해 rank를 저장하는 map도 활용했다.

미처 생각하지 못했던것

  • 다른 사람의 코드에 비해 시간이 오래 걸렸다. map 자료구조를 여러번 사용해서 그런 것으로 추정된다. 더 효율적인 방법을 찾아봐야겠다.

코드

#include<iostream>
#include<string>
#include<vector>
#include<map>
using namespace std;
struct DisjointSet {
    map<string, int> m, rank;
    map<string, string> parent;
    string find(string u) {
        if (u == parent[u]) return u;
        return parent[u] = find(parent[u]); //find 최적화를 위한 작업, 부모가 같은 것들에 대해 동일한 부모로 바꿔준다.
    }

    void merge (string u, string v) {
        u = find(u); v = find(v);
        if (u == v) return;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        m[v] += m[u];
        if (rank[u] == rank[v]) ++rank[v];
    }
};
int main(void)
{
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  int T;

  cin>>T;
  for(int i = 0 ; i<T ; i++)
  {
    struct DisjointSet DJS;
    int F;
    cin>>F;
    for(int j = 0 ; j<F ; j++)
    {

      bool friend1_flag = 0, friend2_flag = 0;
      string friend1, friend2;
      cin>>friend1>>friend2;
      if(DJS.parent.find(friend1) == DJS.parent.end())
      {
        DJS.m.insert({friend1,1});
        DJS.parent.insert({friend1,friend1});
        DJS.rank.insert({friend1,1});
      }
      if(DJS.parent.find(friend2) == DJS.parent.end())
      {
        DJS.m.insert({friend2,1});
        DJS.parent.insert({friend2,friend2});
        DJS.rank.insert({friend1,2});
      }
      DJS.merge(friend1, friend2);
      cout<<DJS.m.find(DJS.find(friend2))->second<<'\n';
    }
  }
  return 0;
}