Cod sursa(job #527448)

Utilizator avram_florinavram florin constantin avram_florin Data 31 ianuarie 2011 17:06:34
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<fstream>

using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

int N,M,viz[100001];

typedef struct node{
		int x;
		node *urm;
		} *Pnod;
Pnod v[100001];

void add(Pnod &dest,int val)
{
	Pnod p;
	p = new node;
	p -> x = val;
	p -> urm = dest;
	dest = p;
}

void dfs(int nod)
{
	viz[nod] = 1;
	Pnod p;
	for( p = v[nod] ; p != NULL ; p = p -> urm )
		if( viz[p->x] )
			dfs(p->x);
}

int main(void)
{
	f >> N >> M;
	int i,x,y;
	for( i = 1 ; i <= M ; i++ )
		{
			f >> x >> y;
			add(v[x],y);
			add(v[y],x);
		}
	int nr = 0;
	for( i = 1 ; i <= N ; i++ )
		if( !viz[i] )
			{
				nr++;
				dfs(i);
			}
	g << nr << '\n';
	f.close();
	g.close();
	return 0;
}