Cod sursa(job #657194)

Utilizator noobakafloFlorin eu noobakaflo Data 5 ianuarie 2012 22:17:20
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#define N_MAX 100001

struct lista
{
	int nod;
	lista *next;
} *G[N_MAX];

long n,m,nr; bool vizitat[N_MAX];

void Adauga(long i, long j)
{
	lista *q;
	q=new lista;   q->nod=j;
	q->next=G[i];  G[i]=q;
}	

void Citire(void)
{
	long i,j;
	freopen("dfs.in","r",stdin);
	scanf("%d %d\n",&n,&m);
	for(; m>0; m--)
	{
		scanf("%d %d\n",i,j);
		Adauga(i,j); Adauga(j,i);
	}
}

void DFS(long nod)
{
	lista *q;
	vizitat[nod]=1;
	for(q=G[nod]; q!=NULL; q=q->next)
		if(!vizitat[q->nod])
			DFS(q->nod);
}

void Solve(void)
{
	int i;
	for(i=1; i<=n; i++)
		if(!vizitat[i])
		{
			nr++;
			DFS(i);
		}
}

void Afisare(void)
{
	freopen("dfs.out","w",stdout);
	printf("%d\n",nr);
}	
		

int main()
{
	Citire();
	Solve();
	Afisare();
	return 0;
}