Cod sursa(job #698428)

Utilizator antrax33laura tuliu antrax33 Data 29 februarie 2012 13:58:32
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>

using namespace std;

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

struct tnod
{
	tnod *first,*last,*next,*haspar;
	int val,chk;
};

tnod *a[1005],*p1,*p2;
int x,y,n,m,nb,i;

void link(tnod *a, tnod *b);
int dfs(tnod *p);

int main()
{
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		p1=new tnod; p1->val=x; p1->chk=0;
		p1->first=NULL; p1->last=NULL; p1->next=NULL; p1->haspar=NULL;
		p2=new tnod; p2->val=y; p2->chk=0;
		p2->first=NULL; p2->last=NULL; p2->next=NULL; p2->haspar=NULL;
		int ok1=0,ok2=0;
		if(a[x]==NULL) {a[x]=p1; ok1=1;}
		if(a[y]==NULL) {a[y]=p2; ok2=1;}
		if(ok1 || ok2) link(a[x],a[y]);
	}
	for(i=1;i<=n;i++)
		if(a[i]==NULL)
		{
			p1=new tnod; p1->val=i; p1->chk=0;
			p1->first=NULL; p1->last=NULL; p1->next=NULL; p1->haspar=NULL;
			a[i]=p1;
		}
	int j=1;
	while(j<=n)
	{
		nb++; dfs(a[j]);
		while(a[j]->chk==1) j++;
	}
	g<<nb;
	g.close();
	f.close();
	return 0;
}

void link(tnod *a, tnod *b)
{

	if(a->first==NULL) a->first=b;
	if(b->first==NULL) b->first=a;
	if(b->last!=NULL) {b->last->next=a; b->last->haspar=b;}
	if(a->last!=NULL) {a->last->next=b; a->last->haspar=a;}
	b->last=a; a->last=b;
	if(b->last!=b->first) a->haspar=b;
	if(a->last!=a->first) b->haspar=a;
}

int dfs(tnod *p)
{
	if(p==NULL) return 0;
	p->chk=1;
	tnod *t=p->first;
	if(t==NULL) return 0;
	while(t!=NULL)
	{
		if(t->chk==0) dfs(t);
		t=t->next;
	}
	return 1;
}