백준 3780번 : 네트워크 연결 - Union&Find dis-joint set C++

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

3780번: 네트워크 연결

1.문제설명

Union & Find, dis-joint set을 이용하는 문제입니다.

재귀를 잘 이용해서 거리를 잘 구해야 풀 수 있습니다.

 

 

부가적으로 제가 50%에서 계속 틀렸는데

거리를 구할 때 (i-j)%1000 이고

답을 구할 때 %1000을 해주면 안됩니다.

답은  (i-j)%1000을 모두 합한 값입니다

즉 1000을 넘어갈 수 도 있기 때문에 답에도 %1000을 해버리면 틀립니다.

 

 

 

 

---

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;


int d[20003];
int unf[20003];


int Find(int x) {
	if (unf[x] < 0) return x;
	int idx = Find(unf[x]);

	d[x] += d[unf[x]];
	return unf[x] = idx;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	for (int T = 0; T < t; T++) {
		memset(unf, -1, sizeof(unf));
		memset(d, 0, sizeof(d));
		int n;
		cin >> n;

		char c;

		while (1) {
			cin >> c;

			if (c == 'E') {
				int k;
				cin >> k;
				Find(k);
				cout << d[k] << '\n';
			}
			else if (c == 'I') {
				int a, b;
				cin >> a >> b;
				unf[a] = b;
				d[a] = (abs(a - b) % 1000);
			}
			else if (c == 'O') {
				break;
			}
		}
	}

	return 0;
}