Cod sursa(job #833340)

Utilizator Kira96Denis Mita Kira96 Data 12 decembrie 2012 14:41:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int nr,viz[100001],k,n,m,x,y;
struct nod
{
	int inf;
	nod *adr;
}*l[100001];
void create(int i,int j)
{
	nod *c=new nod;
	c->inf=j;
	c->adr=l[i];
	l[i]=c;
}
void dfs(int a)
{
	nod *c=l[a];
	viz[a]=1;
	for(;c;c=c->adr)
		if(!viz[c->inf])
		{
			viz[c->inf]=1;
			dfs(c->inf);
		}
}
int main ()
{
	f>>n>>m;
	for(k=1;k<=m;++k)
	{
		f>>x>>y;
		create(x,y);
		create(y,x);
	}
	for(k=1;k<=n;++k)
	{
		if(!viz[k])
		{
			dfs(k);
			++nr;
		}
	}
	g<<nr;
	return 0;
}