[백준OJ] 4195번 친구 네트워크

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

4195번: 친구 네트워크

---

 

 

풀이

입력받은 이름들을 숫자로 매핑해준뒤, Find-Union 알고리즘을 이용해서 네트워크를 연동시켜준다. 이때, 연결하고 카운팅을 하면 시간초과가 날 수 있으므로, 네트워크를 연결함과 동시에, 부모노드에 다른하나에 연결된 노드의 cnt를 더해준뒤, 부모노드의 cnt를 리턴해주면 시간초과가 나지 않고 값을 바로 구할 수 있게된다.

또한, 친구관계를 최대 100,000개 입력받는다 했으므로, parent배열은 최악의 수를 고려해서 2배인 200,001개를 할당해주어야 한다.

 

코드

#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
typedef struct node {
	int pa;
	int cnt;
}node;
int t, n;
node parent[200010];

int find(int a) {
	if (a == parent[a].pa) {
		return a;
	}
	else return find(parent[a].pa);
}


int union_parent(int a, int b) {
	a = find(a);
	b = find(b);
	//서로 다른 두 집합일때
	if (a > b) {
		parent[a].pa = b;//집합 union
		parent[b].cnt += parent[a].cnt;//부모노드에 cnt 추가
		return parent[b].cnt;
	}
	else if(a<b){
		parent[b].pa = a;//집합 union
		parent[a].cnt += parent[b].cnt;//부모노드에 cnt추가
		return parent[a].cnt;
	}
	//같은집합이면 바로 리턴
	else {
		return parent[a].cnt;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--) {
		map<string, int> p;
		int total = 0;
		cin >> n;
		for (int i = 0; i < 200010; i++) {
			parent[i] = { i,1 };
		}
		
		for (int i = 0; i < n; i++) {
			string n1, n2;
			cin >> n1 >> n2;
			if (!p[n1]) {
				p[n1] = ++total;
			}
			if (!p[n2]) {
				p[n2] = ++total;
			}
			int i1 = p[n1];
			int i2 = p[n2];
			cout << union_parent(i1, i2) << "\n";
		}
	}
	return 0;
}