并查集。从后往前加边。
#include#include #include #include using namespace std;const int maxn = 1000000 + 10;int father[maxn], u[maxn], v[maxn], Q, q[maxn], ans[maxn], ff[maxn];int find(int x){ if (x != father[x]) father[x] = find(father[x]); return father[x];}int main(){ int n, m, i; while (~scanf("%d%d", &n, &m)) { memset(ff, 0, sizeof(ff)); for (i = 0; i <= n; i++) father[i] = i; for (i = 1; i <= m; i++) scanf("%d%d", &u[i], &v[i]); scanf("%d", &Q); for (i = 1; i <= Q; i++){ scanf("%d", &q[i]); ff[q[i]] = 1; } int tot = n;//没有边的时候有n个集合 for (i = 1; i <= m; i++) { if (ff[i] == 0) { int uf, vf; uf = find(u[i]); vf = find(v[i]); if (vf != uf) { father[vf] = uf; tot--; //加入一条边，集合少一个 } } } ans[1] = tot; int j = 2; for (i = Q; i > 1; i--) { int uf, vf; uf = find(u[q[i]]); vf = find(v[q[i]]); if (vf != uf) { father[vf] = uf; tot--; //加入一条边，集合少一个 } ans[j] = tot; j++; } for (i = Q; i >= 1; i--) { if (i > 1) printf("%d ", ans[i]); else printf("%d\n", ans[i]); } } return 0;}