[백준 BOJ 4195 glod2 - 친구 네트워크] 해시, 분리집합(disjoint set / union find) C++

백준 4195 친구 네트워크 

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

4195번: 친구 네트워크

 

친구 관계 정보를 받아 친구 네트워크에 속하는 친구 수를 출력하는 문제로, 분리 집합(disjoint set)을 이용하여 풀었다. 

숫자가 아니라 문자열을 입력 받으므로 자료구조 map을 이용하여 <문자열, 정수> 로 저장하여 정수로 처리했다. 

 

union find 설명 글

https://steptoprogrammer.tistory.com/64

[알고리즘/자료구조] 분리 집합( Disjoint Set (a.k.a Union & Find) ) 코드 구현 C++ , 집합 크기 구하기

 

int N, T;
int parent[200001];
int set_size[200001];

int Find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = Find(parent[x]);
}
void Union(int x, int y) {
	int px = Find(x);
	int py = Find(y);
	if (px != py) {
		parent[px] = py;
		set_size[py] += set_size[px];
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> T;
	string s,a;

	for (int i = 0; i < T; i++) {
		cin >> N;

		int cnt = 0;
		map <string, int> pair;
        
        /*for (int i = 1; i <= 200001; i++) {
			parent[i] = i;
			set_size[i] = 1;
		}*/
		
		for (int j = 0; j < N; j++) {
			cin >> s >> a;
			if (pair.find(s) == pair.end()) {
				pair[s] = ++cnt;
				parent[cnt] = cnt;
				set_size[cnt] = 1;
			}
			if (pair.find(a) == pair.end()) {
				pair[a] = ++cnt;
				parent[cnt] = cnt;
				set_size[cnt] = 1;
			}
			int hs = pair[s];
			int ha = pair[a];
			
			Union(hs, ha);
			int net = set_size[Find(hs)];
			cout << net << "\n";
		}
	}
}

map에 없는 문자열일 경우 문자열을 key로 하여 정수 value값을 지정한다. 

정수 값으로 union 과 find 연산을 한다.

 

처음에 주석친 코드로 각 케이스를 돌 때마다 parent, set_size 배열을 초기화 했더니 출력 초과가 났다. 

pair에 추가 할 때 해당 부분만 초기화 하는 코드로 바꾸니까 출력 초과가 나지 않았다..

 

(시간초과가 아니라 왜 출력초과가 난건지는 모르겠다..)