취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16911번 문제인 그래프와 쿼리이다.
문제는 아래 링크를 확인하자.

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

주어진 문제는 offline dynamic connectivity problem으로 불리는 문제로 다음과 같은 분할정복 해법이 잘 알려져있다.

주어진 각 쿼리들에 1부터 M까지의 번호를 붙이고, 에지 없이 N개의 노드로 이루어져 있는 그래프 G와 구간 [1,M]에 대하여 다음을 반복한다:

1) 현재 다루는 구간을 [L,R]이라 하자.

2) L번 쿼리부터 R번 쿼리까지 진행하는 동안 항상 존재하는 에지 가운데 현재 G에 없는 에지들을 G에 추가한다.

3) L==R이고 이 쿼리가 연결성을 묻는 쿼리라면 이에 대한 해답을 구한다.

4) [L,(L+R)/2]구간과 [(L+R)/2+1,R]구간에 대해 이를 반복한다.

5) 과정2에서 추가한 에지를 모두 지운다.

이를 빠르게 진행하기 위해, 그래프 G의 연결상태를 나타내는 자료구조로 rank compression을 이용한 disjoint set을 이용하자. 에지의 추가와 삭제 순서는 위의 과정을 거칠 경우 LIFO의 형태를 갖추므로, 과정2에서의 disjoint set의 조작을 stack자료구조를 이용해 기록을 남겨두면 역순으로 disjoint set을 이전단계로 간단히 돌려놓을 수 있게 됨을 관찰할 수 있다. 즉, 과정5를 빠르게 진행할 수 있게 된다.

또한, 2번 과정에서 추가해야하는 에지가 무엇인지를 빠르게 알아내기 위해 "lazy propagation을 이용하는 segment tree에서 나중에 처리해야할 구간을 저장하는 것"과 같은 방식으로 미리 전처리해두자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
#include <utility>
using namespace std;

int uf[100001], cnt[100001];

vector<pair<pair<int, int>,int>> stk; // {{아래로 들어간 노드,부모노드},cnt변동}

int findf(int cur) {
	if (cur == uf[cur]) return cur;
	return findf(uf[cur]);
}

void unionf(int x, int y, int& tmp) {
	x = findf(x), y = findf(y);
	if (x != y) {
		tmp++;
		if (cnt[x] < cnt[y]) {
			uf[x] = y;
			stk.emplace_back(make_pair(make_pair(x, y), 0));
		}
		else if (cnt[x] > cnt[y]) {
			uf[y] = x;
			stk.emplace_back(make_pair(make_pair(y, x), 0));
		}
		else {
			uf[x] = y, cnt[y]++;
			stk.emplace_back(make_pair(make_pair(x, y), 1));
		}
	}
}

map<pair<int, int>, int> mp;

struct edge {
	int x, y; // 노드 x와 y를 잇는 에지; L==R일 시 x와 y가 이어져있는지 묻는 쿼리
	int L, R; // L번쿼리로 생성, R번쿼리로 소멸; L==R일 시 connectivity 쿼리
	edge(int x, int y, int L, int R) {
		this->x = x, this->y = y, this->L = L, this->R = R;
	}
};

int N, M;

vector<edge> seg[262145];
void segupd(int L, int R, int sI, edge e) {
	if (e.R < L || R < e.L) return;
	else if (e.L <= L && R <= e.R) seg[sI].emplace_back(e);
	else segupd(L, (L + R) / 2, sI * 2, e), segupd((L + R) / 2 + 1, R, sI * 2 + 1, e);
}

void solve(int L, int R, int sI) {
	int tmp = 0;
	for (auto& e : seg[sI]) {
		if (e.L != e.R) unionf(e.x, e.y, tmp);
	}

	if (L == R) {
		for (auto& e : seg[sI]) {
			if (e.L == e.R) {
				if (findf(e.x) == findf(e.y)) cout << 1 << '\n';
				else cout << 0 << '\n';
			}
		}
	}
	else {
		solve(L, (L + R) / 2, sI * 2);
		solve((L + R) / 2 + 1, R, sI * 2 + 1);
	}

	while (tmp--) {
		auto& ee = stk.back();
		uf[ee.first.first] = ee.first.first;
		if (ee.second) cnt[ee.first.second]--;
		stk.pop_back();
	}
}

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

	cin >> N >> M; M++;

	for (int i = 1; i <= N; i++) uf[i] = i;

	for (int i = 1; i < M; i++) {
		int q, A, B; cin >> q >> A >> B;
		if (A > B) swap(A, B);

		if (q == 1) {
			mp.insert(make_pair(make_pair(A, B), i));
		}
		else if (q == 2) {
			int L = mp[make_pair(A, B)];
			segupd(1, M, 1, edge(A, B, L, i));
			mp.erase(make_pair(A, B));
		}
		else {
			segupd(1, M, 1, edge(A, B, i, i));
		}
	}
	for (auto& p : mp) {
		int A = p.first.first, B = p.first.second, L = p.second;
		segupd(1, M, 1, edge(A, B, L, M));
	}

	solve(1, M, 1);
}