Cod sursa(job #505024)

Utilizator siminescuPaval Cristi Onisim siminescu Data 30 noiembrie 2010 09:19:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<fstream>
#include<vector>
using namespace std;

#define nmax 100002

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

vector <int> nod[nmax];
int n,m,viz[nmax],l[nmax];

void citire()
{
	f>>n>>m;
	int i,a,b;
	
	for(i=1;i<=m;i++)
	{
		f>>a>>b;
		nod[a].push_back(b);
		nod[b].push_back(a);
	}
	for(i=1;i<=n;i++) l[i]=nod[i].size();
}
void dfs(int x)
{
	int i;
	viz[x]=1;
	for(i=0;i<l[x];i++) if(!viz[nod[x][i]]) dfs(nod[x][i]);
}
int main()
{
	citire();int i,nr=0;
	for(i=1;i<=n;i++)
		if(!viz[i]) {nr++; dfs(i);}
		g<<nr;
}