[백준 4195] 친구 네트워크 (C++)

문제 링크: https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

1. 주의할 점

- Union-find와 함께 친구의 수를 저장하는 배열이 필요하다

- 이미 같은 집합에 속해 있는 경우, 추가적인 작업을 진행하지 않는다

 

2. 구현

- Find_parent(x) : X의 부모 Node를 되돌려 받는다

- Make_union(a, b): A의 부모와 B의 부모가 일치하지 않는다면, A의 부모와 B의 부모중에서 Index번호가 적은 값이 부모가 되도록 설정 + Index가 높았던 번호의 친구수를 Index가 작았던 번호의 친구수에 합해서 저장한다.

- Map을 통해 이미 입력받은 친구인지 아닌지 판단한다 -> 검색하는데 Log(N)의 시간 복잡도를 소요하므로 효율적!

 

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
map<string, int> m;
int parent[200001];
int friend_num[200001];

int find_parent(int x) {
	if (parent[x] == x) return x;
	return parent[x] = find_parent(parent[x]);
}

void make_union(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) {
		parent[b] = a;
		friend_num[a] += friend_num[b];
	}
	else if(a>b){
		parent[a] = b;
		friend_num[b] += friend_num[a];
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, cnt, num;
	string str1, str2;
	map<string, int> ::iterator it;
	cin >> test;
	for (int t = 0; t < test; t++) {
		m.clear();
		cnt = 0;
		for (int i = 0; i < 200001; i++) {
			parent[i] = i;
			friend_num[i] = 1;
		}

		cin >> num;
		int a, b;
		for (int i = 0; i < num; i++) {
			cin >> str1 >> str2;
			it = m.find(str1);
			if (it == m.end()) {
				m[str1] = ++cnt;
				a = cnt;
			}
			else a = it->second;

			it = m.find(str2);
			if (it == m.end()) {
				m[str2] = ++cnt;
				b = cnt;
			}
			else b = it->second;
			make_union(a, b);
			int root = find_parent(a);
			cout << friend_num[root] << '\n';
		}
	}
	system("pause");
	return 0;
}