Cod sursa(job #475803)

Utilizator mihai995mihai995 mihai995 Data 8 august 2010 16:00:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
using namespace std;

struct arc{int x,y;} a[1<<19];
int s[1<<17],n,m;
bool use[1<<17];

ifstream in("dfs.in");
ofstream out("dfs.out");

void set(int x)
{
	use[x]=true;
	for (int i=s[x];i<s[x+1];i++)
		if (!use[a[i].y])
			set(a[i].y);
}

bool cmp(arc a,arc b)
{
	return a.x<b.x;
}

int main()
{
	int i,j,nr=0;
	in>>n>>m;
	for (i=1;i<=m;i++)
	{
		in>>a[i].x>>a[i].y;
		a[i+m].x=a[i].y;
		a[i+m].y=a[i].x;
	}
	m<<=1;
	sort(a+1,a+m+1,cmp);
	for (i=j=1;i<=n;s[i]=j,i++)
		for (;j<=m && a[j].x<i;j++);
	s[n+1]=m+1;
	for (i=1;i<=n;i++)
		if (!use[i])
		{
			set(i);
			nr++;
		}
	out<<nr<<"\n";
	return 0;
}