QHROAD - Phá đường
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n,Q,damaged[100100],q[100100],ans[100100],d[100100],region;
int get(int x)
{
return x==d[x]?x:d[x]=get(d[x]);
}
int main()
{
int m,b[100100],c[100100];
cin >> n >> m >> Q;
region=n;
for (int i=1;i<=n;i++) d[i]=i;
for (int i=0;i<m;i++) scanf("%d%d",b+i,c+i);
for (int i=0;i<Q;i++) scanf("%d",q+i), damaged[--q[i]]=1;
for (int i=0;i<m;i++)
if (!damaged[i])
{
int x=get(b[i]),y=get(c[i]);
if (x!=y) region--, d[x]=y;
}
for (int i=Q-1;i>=0;i--)
{
ans[i]=region;
int x=get(b[q[i]]),y=get(c[q[i]]);
if (x!=y) region--, d[x]=y;
}
for (int i=0;i<Q;i++) printf("%d\n",ans[i]);
}