Cod sursa(job #575818)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 8 aprilie 2011 19:23:13
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>

long i, N, M, j, x, y, ok, a[1001][1001], stiva[1001], viz[1001], nr;

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
		scanf("%ld %ld", &N, &M);
		
		for (i = 1; i <= M; i ++)
		{
			scanf("%ld %ld", &x, &y);
			a[x][y] = 1;
			a[y][x] = 1;
		}
		nr = 0;
		for (i = 1; i <= N; i ++)
		{
			if (viz[i] == 0)
			{
				nr ++;
				stiva[0] = 1;
				stiva[1] = i;
				viz[i] = 1;
				while (stiva[0] > 0)
				{
					ok = 1;
					for (j = 1; j <= N; j ++)
						if (viz[j] == 0 && a[j][stiva[stiva[0]]] == 1)
						{
							stiva[++stiva[0]] = j;
							viz[j] = 1;
							ok = 0;
							break;
						}
					stiva[0] -= ok;
				}
			}
		}
		
		printf("%ld\n", nr);
		
	
	return 0;
}