Cod sursa(job #472587)

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

const char in[] = "dfs.in";
const char out[] = "dfs.out";
const int NMAX = 100005;

//int N, M, *G[N+1], Deg[N+1];
int N, M, nrsol;
int col[NMAX];

typedef struct nod {
	int vf;
	nod *next;
} *PNOD, NOD;

PNOD L[NMAX];

void Add(int i, int j)
{
	PNOD p = (PNOD)malloc(1*sizeof(NOD));
	p->vf = j;
	p->next = L[i];
	L[i] = p;
}

void DF(int nod)
{
	col[nod] = 1;
	PNOD p;
	for (p = L[nod]; p; p=p->next)
		if (!col[p->vf])
			DF(p->vf);
}

int main(void)
{
	int i, j;

	freopen(in, "r", stdin);
	freopen(out, "w", stdout);
/*
	scanf("%d%d", &N, &M);
    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--;
		G[i][Deg[i]++] = j,
			G[j][Deg[j]++] = i;
	}
*/
	scanf("%d%d", &N, &M);
	for (; M; --M)
	{
		scanf("%d%d", &i, &j);
		Add(i,j);
		Add(j,i);
		col[i] = col[j] = 0;
	}
	for (i = 1; i <= N; ++i)
	{
		if (!col[i]) {
			nrsol++; DF(i); }
	}
	printf("%d\n", nrsol);
	
	return 0;
}