Cod sursa(job #650316)

Utilizator lavinia_nLavinia Nastase lavinia_n Data 17 decembrie 2011 20:36:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>

int n, m, vizitat[100005], k;

typedef struct nod {
	int x;
	nod *a;
} *Nod;
Nod v[100005];

void adauga(Nod &dest, int val) {
	Nod p;
	p = new nod;
	p -> x = val;
	p -> a = dest;
	dest = p;
}

void citire() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, x, y;

	for (i = 1; i <= m; i++) {
		scanf("%d %d",&x,&y);
		adauga(v[x], y);
		adauga(v[y], x);
	}
}

void DFS(int nod) {
	Nod p;
	vizitat[nod] = 1;
	for (p = v[nod]; p != NULL; p = p -> a) 
        if (!vizitat[p -> x]) 
             DFS(p -> x);
}	

int main() {
	citire();
	int i;
	for (i = 1; i <= n; i++) 
        if (!vizitat[i]) {
             k++; 
             DFS(i);
             }
	printf("%d\n",k);
	return 0;
}