codeforces #600 div2 D - Harmonious Graph ( disjoint set )

https://codeforces.com/contest/1253/problem/D

처음으로 버츄얼이 아닌 실제 시험에서 4솔을 했다.

 

 

undirected 그래프가 harmonious -> if and only if, For every triple of integers (l,m,r) such that 1≤l<m<r≤n, if there exists a path going from node l to node r, then there exists a path going from node l to node m.

 

무슨말이냐면, 1~n으로 정점에 번호가 매겨져 있을 때, 예를 들면 1과 8이 연결돼 있으면 1~8은 같은 컴포넌트라는 소리다.

 

정점 수 n, 현재 간선 수 m, 간선들이 입력되면 그 그래프를 harmonious하게 만들기 위해 추가돼야 하는 간선들의 최소개수를 출력하는 문제다.

 

1. 간선들을 입력받을 때 u-v (u<v) 꼴로 강제해서 pair<int,int> 배열 형태로 입력받는다. 이떄 uf도 갱신한다.

2. 간선들을 오름차순 정렬한다.

3. 간선 배열을 차례로 순회하며 '유효한' 구간을 찾아서 can 벡터에 pair<int,int> 형태로 넣어준다.

 - 간선 배열에서 (1, 3) 다음에 (2, 6)이라면 can 벡터엔 (1,6)을 넣는 식.

4. can에 저장된 모든 구간에 대해 union find한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> P;
const int MAX = 2e5 + 2;
 
int uf[MAX];
int find(int a) {
	if (uf[a] == -1) return a;
	return uf[a] = find(uf[a]);
}
 
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[a] = b;
	return true;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m; cin >> n >> m;
	fill(uf, uf + MAX, -1);
	P e[MAX];
	vector<P> can;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		if (u > v) swap(u, v);
		merge(u, v);
		e[i] = { u,v };
	}
 
	sort(e, e + m);
 
	int st = e[0].first, en = e[0].second;
	for (int i = 1; i < m; i++) {
		int l = e[i].first, r = e[i].second;
		if (en < l) {
			can.push_back({ st,en });
			st = l, en = r;
		}
		else if (en < r) en = r;
	}
	can.push_back({ st,en });
 
	int ans = 0;
	for (int i = 0; i < can.size(); i++) {
		int l = can[i].first, r = can[i].second;
		for (int j = l + 1; j <= r; j++) {
			if (merge(l, j)) {
				ans++;
			}
		}
	}
	cout << ans << '\n';
}