백준 4195 친구 네트워크

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 유니온 파인드 구조를 사용해서 해결을 하여야 하는 문제입니다. 다만 조금 까다로운게 string을 처리해야 하는 문제입니다.

 

따라서 저는 map을 이용하였고 map<string, pair<string, int> > parent; 을 선언하여

key값은 사람의 이름을 저장하였고 value값은 pair로 저장하였는데

pair의 first값은 key값의 부모의 이름을 저장하였고

pair의 second값은 key값이 속해있는 그래프의 친구 명수를 저장하였습니다.

 

저는 이문제를 아예 다 string으로 처리해서 코드가 좀 지저분하게 작성 되었습니다.

다른분들을 보니 union-find 연산시에는 각 들어오는 친구에게 번호를 부여하여 처리하였는데

그렇게 처리하는게 보기도 좋고 속도도 더빠른 것 같습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <map>
#include <string>

using namespace std;

map<string, pair<string, int> > parent;

pair<string, int> findfunc(string str) {
	if(parent[str].first == str) return make_pair(str, parent[str].second);
	return parent[str] = findfunc(parent[str].first);
}

int merge(string a, string b) {
	a = findfunc(a).first;
	b = findfunc(b).first;

	if(a == b) return parent[b].second;
	if(parent[b].second > parent[a].second) {
		parent[b].second += parent[a].second;
		parent[a].first = b;
		return parent[b].second;
	}
	else {
		parent[a].second += parent[b].second;
		parent[b].first = a;
		return parent[a].second;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T; cin >> T;
	while(T--) {
		parent.clear(); 
		int F; cin >> F;
		for(int i = 0; i < F; i++) {
			string a,b;
			cin >> a >> b;
			if(parent.find(a) == parent.end()) 
				parent.insert(make_pair(a, make_pair(a, 1)));
			if(parent.find(b) == parent.end())
				parent.insert(make_pair(b, make_pair(b, 1)));
			cout<<merge(a, b)<<'\n';
		}
	}
	return 0;
}