BOJ 24452 交易計画 (Trade Plan)

문제 링크입니다.

문제 요약

그래프의 각 정점이 하나의 그룹에 속합니다. 이때, 두 정점 사이를 두 정점이 포함된 그룹의 정점들만 거쳐 오갈 수 있는지 구해야 합니다. 40만 번.

그룹 묶기

일단 같은 그룹이면서 서로 직접 연결되어 있는 정점들을 하나의 연결 요소로 묶습니다. 분리 집합을 이용합시다. 이를 이용해 두 그룹을 이어야 하는 경우를 처리합니다.

띠부띠부간선

주어진 쿼리를 그룹의 쌍에 따라 분류하면, 각 그룹의 쌍마다 두 그룹을 잇는 간선을 붙였다 뗐다 하면서 각 그룹의 쌍마다 답을 구할 수 있습니다. 각 간선이 최대 한 번 붙였다 뗐다 되게 됩니다. 분리 집합에서 경로 압축을 사용하지 않고, 최근 추가한 간선을 추가하지 않은 상태로 되돌리는 기능을 추가하면 이를 구현할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int par[404040], g[404040];
bool ans[404040];

stack<array<int,3>> st;
vector<pll> e, qry;

map<pll, vector<int>> Edge;
map<pll, vector<int>> Query;

int f(int x){
	return par[x] < 0 ? x : f(par[x]);
}

void u(int x, int y, bool flag = 1){
	x = f(x); y = f(y);
	if(x == y) return;
	if(par[x] > par[y]) swap(x, y);
	if(flag) st.push({x, y, par[y]});
	par[x] += par[y];
	par[y] = x;
}

void rollback(){
	while(st.size()){
		auto arr = st.top(); st.pop();
		par[arr[1]] = arr[2];
		par[arr[0]] -= arr[2];
	}
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	memset(par, -1, sizeof(par));
	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		e.push_back({u, v});
	}
	for(int i = 1; i <= n; i++) cin >> g[i];
	for(int i = 0; i < m; i++){
		if(g[e[i].first] == g[e[i].second]) u(e[i].first, e[i].second, 0);
		else if(g[e[i].first] > g[e[i].second]) Edge[{g[e[i].second], g[e[i].first]}].push_back(i);
		else Edge[{g[e[i].first], g[e[i].second]}].push_back(i);
	}
	int Q; cin >> Q;
	for(int i = 0; i < Q; i++){
		int a, b; cin >> a >> b;
		qry.push_back({a, b});
		if(g[a] == g[b]) ans[i] = (f(a) == f(b));
		else if(g[a] > g[b]) Query[{g[b], g[a]}].push_back(i);
		else Query[{g[a], g[b]}].push_back(i);
	}
	for(auto& [key, vec] : Query){
		for(auto& t : Edge[key]) u(e[t].first, e[t].second);
		for(auto& q : vec) ans[q] = (f(qry[q].first) == f(qry[q].second));
		rollback();
	}
	for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
}