백준 13798: 통신망 분할

문제 요약

현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠진 두 개의 통신망에 속한 통신탑들의 갯수의 곱이 되며, 나누어지지 않을 경우 0이다.

욱제는 회사의 요청에 따라 Q번의 제거를 통해 나오는 비용의 합을 구해야 한다.

문제 분류

• 자료 구조
• 분리 집합
• 오프라인 쿼리

문제 풀이

단순히 한 집합을 두 개의 집합으로 분리시키는 문제로 보이지만, 문제의 순서를 반대로 해석하면 두 집합을 병합할 때 비용의 합을 구하는 문제가 된다.

집합의 크기를 알아야 하므로 최상의 노드는 자기 자신이 아닌 해당 집합의 크기를 절댓값으로 가진 음수를 가지도록 하였다.

입력으로 주어진 m개의 간선들 중 r개의 간선을 제외하여 모두 병합하고, r개의 간선 순서를 반전시켜서 순서대로 연결시킨다. 이 때의 비용을 모두 누적시켜서 출력하면 된다.

문제를 반대로 푸는 관점이 필요한 문제였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

int p[100001];
int pass[100001];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] += p[b];
	p[b] = a;
}

int main()
{
	int n, m, q, in, in2;
	unsigned long long res = 0;
	vector<pair<int, int>> v;
	vector<int> r;
	memset(p, -1, sizeof(p));
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &in, &in2);
		v.push_back({ in,in2 });
	}
	for (int i = 0; i < q; i++) {
		scanf("%d", &in);
		in--;
		pass[in] = 1;
		r.push_back(in);
	}
	reverse(r.begin(), r.end());
	for (int i = 0; i < m; i++) {
		if (!pass[i])
			merge(v[i].first, v[i].second);
	}
	for (auto& it : r) {
		if (find(v[it].first) != find(v[it].second)) {
			res += p[find(v[it].first)] * p[find(v[it].second)];
			merge(v[it].first, v[it].second);
		}
	}
	cout << res;
}