Cod sursa(job #540112)

Utilizator selea_teodoraSelea Teodora selea_teodora Data 23 februarie 2011 18:42:41
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
using namespace std;
typedef
struct nod
{
	int nr;
	nod*urm;
}*Pnod;
Pnod l[100000];
int n,viz[100000],contor,i,j,m;
ofstream fout("dfs.out");
void dfs(int start)
{
	viz[start]=1;
	Pnod p;
	for(p=l[start];p!=NULL;p=p->urm)
			if(viz[p->nr]==0)
			dfs(p->nr);
}
				
int main()
{
	ifstream fin("dfs.in");
	fin>>n>>m;
	Pnod p;
	while(fin>>i>>j)
	{
		p=new (nod);
		p->nr=j;
		p->urm=l[i];
		l[i]=p;
		p=new(nod);
		p->nr=i;
		p->urm=l[j];
		l[j]=p;
	}
	fin.close();
	
	for(i=1;i<=n;i++)
		if(viz[i]==0)
		{
			contor++;
			dfs(i);
		}
	fout<<contor;
	fout<<'\n';
	fout.close();
	return 0;
}