Cod sursa(job #472589)

Utilizator TabaraTabara Mihai Tabara Data 25 iulie 2010 19:44:55
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>

const char in[] = "dfs.in";
const char out[] = "dfs.out";

int N, M, nrsol, **G, *Deg, *Col;

void DF(int i)
{
	int j;
	Col[i] = 1;
	for (j = 0; j < Deg[i] && !Col[G[i][j]]; ++j) DF(G[i][j]);
}

int main(void)
{
	int i, j;

	freopen(in, "r", stdin);
	freopen(out, "w", stdout);

	scanf("%d%d", &N, &M);
	Deg = (int*)malloc(N*sizeof(int));
	Col = (int*)malloc(N*sizeof(int));
	G = (int**)malloc(N*sizeof(int*));
	for (i = 0; i < N; ++i)
		G[i] = (int*)malloc(N*sizeof(int));

    for (; M; --M)
	{
		scanf("%d%d", &i, &j);
		Deg[i-1]++, Deg[j-1]++;
	}
	for (i = 0; i < N; Deg[i++] = 0)
		G[i] = (int*)malloc(Deg[i]*sizeof(int));
	fseek(stdin, 0, SEEK_SET);
	scanf("%d%d", &N, &M);
	for (; M; --M)
	{
		scanf("%d%d", &i, &j);
		i--, j--;
		Col[i] = Col[j] = 0;
		G[i][Deg[i]++] = j,
			G[j][Deg[j]++] = i;
	}
	
	for (i = 0; i < N; ++i) 
		if (!Col[i])
			++nrsol, DF(i);

	printf("%d\n", nrsol);
	return 0;
}