Cod sursa(job #394106)

Utilizator b_polarAgape Mihai b_polar Data 10 februarie 2010 16:09:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#define NMAX 100001
using namespace std;

int N,M;
typedef struct nod{int x;nod* nxt;}*LISTA;
void citire(),adaugare(LISTA&,int),DFS(int);
LISTA v[NMAX];
int vizitat[NMAX];

int main()
{
int i,c=0;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
for(i=1;i<=N;i++)
	if(!vizitat[i])DFS(i),c++;
cout<<c;
return 0;
}

void DFS(int x)
{
vizitat[x]=1;
for(LISTA p=v[x];p;p=p->nxt)
	if(!vizitat[p->x])DFS(p->x);
}

void adaugare(LISTA &l, int y)
{
LISTA a = new nod;
a->x = y;
a->nxt = l;
l=a;
}

void citire()
{
int i,x,y;
cin>>N>>M;
for(i=0;i<M;i++)
	{
	cin>>x>>y;
	adaugare(v[x],y);
	adaugare(v[y],x);
	}
}