[백준 3780] 네트워크 연결 (C++)

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

3780번: 네트워크 연결

1. 주의할 점

- TLE가 안나도록 잘 짜야 한다

- 새로운 간선을 연결할때만 1000으로 나눈 나머지 거리로 입력한다

 

2. 구현

- Find_parent(x) 함수를 통해 X의 센터에서부터 X까지의 거리를 구하여 갱신한다. 기존에 1->2->4였고 4->6이 새로 추가 됐다고 가정한다. 그리고 E 1을 입력한 경우, Dist[1], Dist[2]가 새로 갱신된다. Dist[4]의 경우 새로운 간선을 추가할 때 갱신되어 다시 갱신되지는 않는다 

- Make_union(a,b) 함수를 통해 A->B의 간선을 만들며 이때 간선의 길이는 두 Idx의 차이%1000이다. 이후 Par[a]=b를 통해 Par[a]에는 A의 센터를 입력하는것이 아닌, 바로 위인 B와 연결한다

- E를 입력받았을 때마다 Find_parent() 함수를 호출하여 Dist가 갱신될 수 있도록 한다

 

#include <iostream>
#include <algorithm>
using namespace std;
int par[20001];
int dist[20001];
int node;

int find_parent(int x) {
	if (par[x] == x) return x;
	int idx = find_parent(par[x]);
	dist[x] += dist[par[x]];
	return par[x] = idx;
}

void make_union(int a, int b) {
	dist[a] = abs(a - b) % 1000;
	par[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, a, b;
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> node;
		for (int i = 1; i <= node; i++) {
			par[i] = i;
			dist[i] = 0;
		}
		char c;
		while (1) {
			cin >> c;
			if (c == 'O') break;
			else if (c == 'E') {
				cin >> a;
				find_parent(a);
				cout << dist[a] << '\n';
			}
			else if (c == 'I') {
				cin >> a >> b;
				make_union(a, b);
			}
		}
	}
	system("pause");
	return 0;
}