백준 4195 친구 네트워크

문제 출처 :
https://www.acmicpc.net/problem/4195

이름 2개가 한쌍인 input m개가 주어졌을때 그래프에서 가장 많이 이어져 있는 노드 수 를 출력하는 문제이다. m이 100000이기 때문에 Union Find 알고리즘이 들어가야 한다. input이 string 형으로 주어지기 때문에 map을 사용해 이미 있다면 추가시키지 않고 없다면 노드수를 한개 증가시키고 map에 넣어둔다. 그 다음 find로 2개의 노드의 조상을 찾은 뒤 union으로 이어진 최대 노드 수를 업데이트 한다. 매번 m번의 시행마다 해당 결과를 출력한다.

소스코드:

// 친구 네트워크

#include <bits/stdc++.h>

using namespace std;

int sizes[200002];
int par[200002];

int find(int i){
    if(par[i] == i) return i;
    return par[i] = find(par[i]);
}

void Union(int x, int y) {
  int px = find(x), py = find(y);
  
  if( px != py ){
    if (sizes[px] < sizes[py]) swap(px, py);
    sizes[px] += sizes[py];
    par[py] = px;
  }
}

int main(){
  freopen("Input.txt", "r", stdin);

  int T;
  cin>>T;

  while(T--){
    string s1,s2;
    map<string, int> map;

    for (int i = 0; i < 200002; i++) {
			sizes[i] = 1;
			par[i] = i;
		}

		int n = 1, m, px, py;
    cin>>m;
    while(m--){
      cin >> s1 >> s2;

      if (map.count(s1) == 0) map[s1] = n++;		
			if (map.count(s2) == 0) map[s2] = n++;

      Union(map[s1], map[s2]);

      px = find(map[s1]);
      py = find(map[s2]);

      cout << max(sizes[px], sizes[py]) << endl;
    }
  }
}

참고:
https://chanhuiseok.github.io/posts/baek-21/