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;
}