Cod sursa(job #146300)

Utilizator filipbFilip Cristian Buruiana filipb Data 1 martie 2008 15:27:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#include <stdlib.h>

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);
	for (; M; --M)
	{
		scanf("%d %d", &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;
}