Cod sursa(job #607771)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 13 august 2011 14:21:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out");

const int DIM = 100005;
int viz[DIM], N, M, NC;
struct nod { int v; nod *a; } *V[DIM];

void add (int a, int b)
{
	nod *q = new nod;
	q->v = b;
	q->a = V[a];
	V[a] = q;
}

void dfs (int n)
{
	viz[n] = 1;
	int f;
	for (nod *q = V[n]; q != NULL; q = q->a)
	{
		f = q->v;
		if (viz[f] == 0)
			dfs (f);
	}
}

int main ()
{
	fi >> N >> M;
	for (int i = 1; i <= N; i++)
		V[i] = NULL;
	for (int i = 0, a, b; i < M; i++)
	{
		fi >> a >> b;
		add (a, b);
		add (b, a);
	}
	
	for (int i = 1; i <= N; i++)
		if (viz[i] == 0)
		{
			dfs (i);
			NC++;
		}
	
	fo << NC;
	return 0;
}