Cod sursa(job #588613)

Utilizator balakraz94abcd efgh balakraz94 Data 8 mai 2011 20:35:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<cstdio>
#define infile "dfs.in"
#define outfile "dfs.out"
#define L 100005
using namespace std;

typedef struct nod { 
	int info;
	nod *urm;
} *pnod;


void add( pnod&, int);

pnod v[L];

bool uz[L];

int n,m,sol;



void citeste()
{
	freopen(infile,"r",stdin); 
	
	scanf("%d %d",&n,&m);
	
	int x,y;
	
	for(;m>0;m--)
	{
		scanf("%d %d",&x,&y);
		add(v[x],y);
		add(v[y],x);
	}
	
	fclose(stdin);
}


void add(pnod &dest, int val)
{
	pnod p;
	p = new nod;
	p->info=val;
	p->urm=dest;
	dest=p;
}


void dfs(int k)
{
	uz[k]=1;
	
	pnod p;
	
	for(p=v[k]; p!=NULL;p=p->urm)
		if(!uz[p->info])
			dfs(p->info);
}


void rezolva()
{
	for(int i=1;i<=n;i++)
		if(!uz[i])
			dfs(i), sol++;
}


void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",sol);
	
	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}