Cod sursa(job #699231)

Utilizator antrax33laura tuliu antrax33 Data 29 februarie 2012 18:20:28
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>

using namespace std;

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

struct tnod
{
	int first,last,next,haspar;
	int val,chk;
} a[100001];

int x,y,n,m,nb,i,ch[100001];

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

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

void link(int x,int y)
{
	if(a[x].first==0) a[x].first=y;
	if(a[y].first==0) a[y].first=x;
	if(a[y].last!=0) {a[a[y].last].next=x; a[a[y].last].haspar=y;}
	if(a[x].last!=0) {a[a[x].last].next=y; a[a[x].last].haspar=x;}
	a[y].last=x; a[x].last=y;
	if(a[y].last!=a[y].first) a[x].haspar=y;
	if(a[x].last!=a[x].first) a[y].haspar=x;
}

void dfs(int p)
{
	a[p].chk=1;
	int t=a[p].first;
	while(t!=0)
	{
		if(a[t].chk==0) dfs(t);
		t=a[t].next;
	}
}