Cod sursa(job #548408)

Utilizator aplace4uheadaplace4uhead aplace4uhead Data 7 martie 2011 14:10:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream.h>
#define NM 100001

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

struct nod
{
	int nr;
  nod *next;
};

nod *l[NM],*urm[NM];
int n,m,viz[NM],cc;

void add(nod *&l,int x)
{
	nod*nn=new(nod);
	nn->nr=x;
	nn->next=l;
  l=nn;
}

void build()
{
	int i,x,y;
	in>>n>>m;
	for(i=0;i<m;i++)
	{
		in>>x>>y;
		add(l[x],y);
		add(l[y],x);
	}
}

void df(int x)
{
	int y;
  nod *nc=urm[x];
	while(nc)
	{
		viz[x]=cc;
		y=nc->nr;
		nc=nc->next;
		if(!viz[y]) df(y);
		urm[x]=nc;
	}
}

int main()
{
	int i;
	build();
	for(i=1;i<=n;i++)
		urm[i]=l[i];
	for(i=1;i<=n;i++)
		if(!viz[i])
		{
			cc++;
			df(i);
		}
	fout<<cc;
  return 0;
}