Cod sursa(job #146297)

Utilizator filipbFilip Cristian Buruiana filipb Data 1 martie 2008 15:23:56
Problema Parcurgere DFS - componente conexe Scor Ascuns
Compilator cpp Status done
Runda Marime 0.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define ll long long
#define minim(a, b) ((a < b) ? a : b)

typedef struct lista { int id; struct lista* next; };
typedef lista *Graf[100005];

int N, M, conex;
char uz[100005];
Graf G;

void add_to_list(lista **l, int item)
{
	lista *tmp = (lista *)malloc(sizeof(lista));
	tmp->id = item;
	tmp->next = *l;
	*l = tmp;
}

void df(int nod)
{
	lista *f;

	uz[nod] = 1;
	for (f = G[nod]; f; f = f->next)
		if (!uz[f->id])
			df(f->id);
}

int main(void)
{
	int i, j;
	
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%d %d", &N, &M);
	assert(1 <= N && N <= 100000);
	assert(0 <= M && M <= minim((ll)N * (N+1)/2, 200000));
	for (; M; --M)
	{
		scanf("%d %d", &i, &j);		
		assert(1 <= i && i <= N);
		assert(1 <= j && j <= N);
		assert(i != j);
		add_to_list(&G[i], j);
		add_to_list(&G[j], i);	
	}
	
	for (i = 1; i <= N; i++)
		if (!uz[i])
		{
			++conex;
			df(i);
		}
	
	printf("%d\n", conex);
	
	return 0;
}