Cod sursa(job #301994)

Utilizator cristiprgPrigoana Cristian cristiprg Data 8 aprilie 2009 16:27:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#define DIM 2050

int a[DIM][DIM], n, m, count, v[DIM];

void DFS(int i)
{
	v[i] = 1;
	for (int j = 1; j <= a[i][0]; j++)
		if (!v[ a[i][j] ])
			DFS(a[i][j]);
}


int main()
{
	FILE *f = fopen("dfs.in", "r");
	fscanf(f, "%d%d", &n, &m);
	int i, x, y;
	for (i = 1; i <= m; i++)
	{
		fscanf(f, "%d%d", &x, &y);
		a[x][ ++a[x][0] ] = y;
		a[y][ ++a[y][0] ] = x;
	}

	fclose(f);
/*	for (i = 1; i <= n; i++)
	{
		for (int j = 1; j <= a[i][0]; j++)
			printf("%3d", a[i][j]);

		printf("\n");
	}
*/
	for (i = 1; i <= n; i++)
		if (!v[i])
			count++,DFS(i);

	f = fopen("dfs.out", "w");
	fprintf(f, "%d\n", count);
	fclose(f);

	return 0;
}