Cod sursa(job #322658)

Utilizator GulyanAlexandru Gulyan Data 9 iunie 2009 16:07:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
	int cul;
	int *vec;
	int m;
}Nod;

typedef struct{
	int s, d;
}Arc;

#define ALB 0
#define GRI 1
#define NEGRU 2

int *S, vf;
Nod *v;

void DFS(int i)
{
	int j, k;
	v[i].cul = GRI;
	for( j = v[i].m ; j--; ){
		k = v[i].vec[j];
		if(v[k].cul == ALB)
			DFS( k );
	}
	//S[vf++] = i;
	v[i].cul = NEGRU;
}

int main(int argc, char *argv[])
{
	//deschidere fisiere
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	//declarare date, initializare, citire si alocare de memorie
	Arc *a;
	int n, m, i;
	scanf("%d%d", &n, &m);
	n++;
	v = (Nod*)malloc( sizeof(*v) * n );
	a = (Arc*)malloc( sizeof(*a) * m );
	int *laf, *la;
	laf = la = (int*)malloc( sizeof(int) * m<<1 );
	S = (int*)malloc( sizeof(int) * n );
	for( i = 0; i < n; i++){
		v[i].cul = ALB;
		v[i].m = 0;
	}
	for( i = 0; i < m; i++){
		scanf("%d%d", &a[i].s, &a[i].d);
		v[a[i].s].m++;
		v[a[i].d].m++;
	}

	//crearea listelor de adiacenta
	for( i = 0; i < n; i++){
		v[i].vec = la;
		la += v[i].m;
		v[i].m = 0;
	}
	for( i = 0; i < m; i++){
		//for( j = 0; j < v[a[i].s].m; j++)
		//	if(v[a[i].s].vec[j] == a[i].d)
		//		continue;
		v[a[i].s].vec[v[a[i].s].m++] = a[i].d;
		v[a[i].d].vec[v[a[i].d].m++] = a[i].s;
	}

	vf = 0;
	for( i = 1; i < n; i++){
		if(v[i].cul == ALB){
			//Parcurgere DFS
			DFS( i );
			vf++;
		}
	}

	printf("%d\n", vf);

	//for( i = vf; i--; )
		//printf("%d ", S[i]);

	//eliberare memorie
	free( a );
	free( v );
	free( S );
	free( laf );
	return 0;
}