백준 17398번 : 통신망 분할 - Union & Find dis-joint set 알고리즘 C++

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

17398번: 통신망 분할

 

1. 문제설명

노드를 이어주는 간선을 제거했을 때

컴포넌트의 수가 증가한다면 각 컴포넌트의 노드 개수를 곱해서 결괏값에 더해야합니다.

이 문제는 이 방법대로 해결하기보다 역으로 생각해야 쉽게 풀 수 있습니다.

 

 

---

2.접근방법[알고리즘]

 

Union & Find 알고리즘을 응용합니다.

분할의 반대는 병합입니다. 

간선을 제거할 때 나눠지는 컴포넌트 노드의 수를 곱하는 대신

병합하기전 컴포넌트의 노드의 수를 곱하고 병합하면 더 쉽게 해결할 수 있습니다.

 

 

 

---

3.문제풀이코드 C++

 

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

int n, m, q;
vector<pair<int, int> > v(1);
bool ch[100003];
vector<int> del;
int unf[100003];

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

	return unf[x] = Find(unf[x]);
}

//루트에 하위 노드의 개수를 저장합니다
void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a == b) return;

	if (unf[a] <= unf[b]) {
		unf[a] += unf[b];
		unf[b] = a;
	}
	else {
		unf[b] += unf[a];
		unf[a] = b;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(unf, -1, sizeof(unf));

	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	for (int i = 0; i < q; i++) {
		int a;
		cin >> a;
		ch[a] = 1;
		del.push_back(a);
	}

	for (int i = 1; i <= m; i++) {
		if (ch[i] == 0) {
			Union(v[i].first, v[i].second);
		}
	}

	long long ans = 0;
	for (int i = del.size() - 1; i >= 0; i--) {
		int a = v[del[i]].first;
		int b = v[del[i]].second;

		if (Find(a) != Find(b)) {
			ans += (unf[Find(a)] * unf[Find(b)]);
		}
		Union(a, b);
	}

	cout << ans << '\n';


	return 0;
}

백준 17398 통신망 분할

주의할점 : 정답이 INT_MAX를 넘어갑니다.