Cod sursa(job #397998)

Utilizator UnOrdinaryVyper Boy UnOrdinary Data 17 februarie 2010 20:18:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>
using namespace std;
#define N 100001

int viz[N],n,m;

struct nod
{
	int info;
	nod *urm;
}*l[N],*p;

void dfs( int k)
{
	nod *pi;
	viz[k]=1;
	for (pi=l[k];pi!=NULL;pi=pi->urm)
	{
		if (viz[pi->info]==0) dfs(pi->info);
	}
}

int main()
{
	int i,x,y,c=0;
	ifstream fin ("dfs.in");
	ofstream fout ("dfs.out");
	fin>>n>>m;
	for (i=1;i<=m;i++)
	{
		p = new nod;
		fin>>x>>y;
		p->info=y;
		p->urm=l[x];
		l[x]=p;
		p = new nod;
		p->info=x;
		p->urm=l[y];
		l[y]=p;
	}
	for (x=1;x<=n;x++)
	{
		if (viz[x]==0)
		{
			dfs(x);
			c++;
		}
	}
	fout<<c;
}