QHROAD - Phá đường

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5, M = 1e5, Q = 1e5;
int p[N], d[Q], u[M], v[M], n, m, q, nset, res[Q];
bool del[M];

void enter() {
	cin >> n >> m >> q;
	for(int i = 0; i < m; ++i)
		cin >> u[i] >> v[i], --u[i], --v[i];
	for(int i = 0; i < q; ++i)
		cin >> d[i], del[--d[i]] = true;
}

void reset(int n) {for(int i = 0; i < n; ++i) p[i] = i; nset = n;}
int getset(int u) {return u == p[u] ? u : p[u] = getset(p[u]);}
void joint(int u, int v) {if(getset(u) != getset(v)) p[p[u]]=p[v], --nset;}

void solve() {
	reset(n);
	for(int i = 0; i < m; ++i) if(!del[i]) joint(u[i], v[i]);
	for(int i = q-1; i >= 0; --i) res[i] = nset, joint(u[d[i]], v[d[i]]);
	for(int i = 0; i < q; ++i) cout << res[i] << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	solve();
	return 0;
}

Download