Cod sursa(job #238822)

Utilizator ilincaSorescu Ilinca ilinca Data 3 ianuarie 2009 12:58:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>

#define nmax 100005

struct nod
{
	int x;
	nod *next;
};

int n, m;
bool viz [nmax];
nod *first [nmax];


void insert (int poz, int v)
{
	nod *aux;
	aux=new nod;
	aux->x=v;
	if (first [poz] == NULL)
	{
		aux->next=NULL;
	}
	else
	{
		aux->next=first [poz];
	}
	first [poz]=aux;
}

void scan ()
{
	int a, b;
	scanf ("%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		scanf ("%d%d", &a, &b);
		insert (a, b);
		insert (b, a);
	}
}

void dfs (int x)
{
	viz [x]=true;
	for (nod *i=first [x]; i != NULL; i=i->next)
		if (viz [i->x] == false)
			dfs (i->x);
}

int res ()
{
	int num=0;
	for (int i=1; i<=n; ++i)
		if (viz [i] == false)
		{
			dfs (i);
			++num;
		}
	return num;
}

int main ()
{
	freopen ("dfs.in", "r", stdin);
	freopen ("dfs.out", "w", stdout);
	scan ();
	printf ("%d\n", res ());
	return 0;
}