https://www.acmicpc.net/problem/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;
}

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

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

1. 문제설명

영어로 된 문제여서 구글 번역을 한번 돌리면 좀 더 쉽게 이해가 가능합니다.

Union & Find 알고리즘을 이용하여 문제를 해결했습니다.

N개의 Haybale을 spiceness에 대해 오름차순으로 정렬합니다.

spiceness가 작은 Haybale 부터 확인하면서 그 Haybale의 위 아래에 있는 Haybale 중

자신보다 spiceness가 작은 게 있으면 Union 해줍니다.

이 과정을 반복하다가

자신이 속한 집단의 flavor 값 합이 M 이상이 된다면

자신의 spiceness를 출력해주면 됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
int n;
long long m;
long long unf[100001];

pair<int, int> arr[100001];

struct Haybale {
	int node, flavor, spicy;
	bool operator<(const Haybale& b)const {
		return spicy < b.spicy;
	}
};

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[b] += unf[a];
		unf[a] = b;
	}
	else {
		unf[a] += unf[b];
		unf[b] = a;
	}
}

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

	cin >> n >> m;
	vector<Haybale> v;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		arr[i] = { a,b };
		v.push_back({ i,a,b });
	}

	for (int i = 1; i <= n; i++) {
		unf[i] = -arr[i].first;
	}


	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		int node = v[i].node;

		if (node - 1 >= 1 && arr[node - 1].second <= arr[node].second) {
			Union(node - 1, node);
		}
		if (node + 1 <= n && arr[node].second >= arr[node + 1].second) {
			Union(node + 1, node);
		}

		if (-unf[Find(node)] >= m) {
			cout << arr[node].second;
			return 0;
		}
	}


	return 0;
}

m의 범위에 유의해야 메모리초과와 런타임에러를 방지할 수 있습니다.