Cod sursa(job #700214)

Utilizator amerigohi lili amerigo Data 1 martie 2012 07:48:07
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
using namespace std;

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

int x,y,n,m,nb,i;

struct tlink {int nod; tlink * next;};
struct tlist {tlink *first,*last;};
int addlast(tlist &list,int nod)
{
	tlink *l=new tlink;
	l->nod=nod;
	if(list.first==NULL) {list.first=l;list.last=l;}
	list.last->next=l;
	list.last=l;
	l->next=NULL;
	return 0;
}
struct tnod {int chk,val; tlist list;} a[10001];
int link(int x, int y)
{
	addlast(a[x].list,y);
	addlast(a[y].list,x);
	return 0;
}
int dfs(int p);

int main()
{
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		a[i].chk=0;
		a[i].val=0;
		a[i].list.first=NULL;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		a[x].val=x;
		a[y].val=y;
		link(x,y);
	}
	i=1;
	while(i<=n)
	{
		nb++; dfs(i);
		while(a[i].chk==1) i++;
	}
	
	
	g<<nb;
	g.close();
	f.close();
	return 0;
}
int dfs(int p)
{
	a[p].chk=1;
	tlink * t=a[p].list.first;
	while(t!=NULL)
	{
		if(a[t->nod].chk==0) dfs(t->nod);
		t=t->next;
	}
	return 0;
}