Решение задачи Компоненты связности с Codeforces

Без пояснения   Просмотров: 1272


В уже известной нам некоторой большой корпорации, в которой работает системный администратор Поликарп, компьютерная сеть состоит n компьютеров и m кабелей, которые соединяют некоторые пары компьютеров. Другими словами, компьютерная сеть может быть представлена некоторым неориентированным графом из n вершин и m ребер. Пронумеруем компьютеры целыми числами от 1 до n, пронумеруем кабели целыми числами от 1 до m.

Код

#include<bits/stdc++.h>

using namespace std;

int u[10005],v[10005];
int rank[505],f[505];
int n,m;
struct dsu{
	int f[505],c;
	int find(int x)
	{
		return f[x]?f[x]=find(f[x]):x;	
	} 
	void merge(int x,int y){
		x=find(x);
		y=find(y);
		if(x!=y) f[x]=y,c++;
	}
};
dsu a[10005],b[10005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i];
		a[i]=a[i-1];
		a[i].merge(u[i],v[i]);
	}
	for(int i=m;i;i--){
		b[i]=b[i+1];
		b[i].merge(u[i],v[i]);
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		dsu ans=a[l-1];
		for(int i=1;i<=n;i++){
			if(b[r+1].f[i])ans.merge(i,b[r+1].f[i]);
		}
		cout<<n-ans.c<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться