[백준 / BOJ] C++ 4195 친구 네트워크

4195번: 친구 네트워크

 

문제

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

4195번: 친구 네트워크

 

 

풀이

친구 네트워크가 연결될 때마다 네트워크에 연결된 사람의 수를 출력하는 문제다. 각 이름에 대해 번호를 부여하기 위해 map 자료 구조를 사용한다. 만약 map에 이름이 없다면 맵의 사이즈를 번호로 사용하게 한다. 이러면 번호가 0번부터 붙게 된다. 또 N번의 연결이 이루어지는데 각 연결마다 두 명의 이름이 주어지므로 최대 2 × N명의 관계를 받을 수 있다.

 

먼저 각 원소는 스스로 크기가 1인 집합이므로 크기를 나타내는 배열 s를 모두 1로 초기화한다. 그리고 입력받은 두 사람을 union 한다.(네트워크로 연결한다.) 단, 항상 부모 노드는 번호가 작은 쪽을 가리키고 집합을 합칠 때도 번호가 작은 쪽으로 합친다. 만약 두 사람이 이미 같은 네트워크에 포함되어 있다면 집합의 크기를 합치면 안 된다.

 

 

코드

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

vector<int> p, s;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x); // 루트 탐색
  y = find(y); // 루트 탐색
  if (x == y) // 만약 같은 집합이면
    return; // 연결하지 않는다
  // 항상 크기가 작은 쪽으로 연결
  if (x > y)
    swap(x, y);
  // 집합의 크기 더하기
  s[x] += s[y];
  // 두 집합 연결
  p[y] = x;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    p.resize(2 * n); // 2×N 크기로 재할당
    iota(p.begin(), p.end(), 0); // 0부터 N-1로 할당
    s.resize(2 * n); // 2×N 크기로 재할당
    fill(s.begin(), s.end(), 1); // 모두 1로 초기화
    map<string, int> M;
    while (n--) {
      string a, b; // 두 사람 이름 입력
      cin >> a >> b;
      if (M.find(a) == M.end()) // 아직 번호가 없다면
        M[a] = M.size(); // 번호 할당
      if (M.find(b) == M.end())
        M[b] = M.size();
      // 두 사람을 연결
      merge(M[a], M[b]);
      // 연결된 사람의 집합의 크기(사이즈 배열의 루트 인덱스) 출력
      cout << s[find(M[a])] << '\n';
    }
  }
  return 0;
}