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

Download