Cod sursa(job #558183)

Utilizator cezyGrigore Cezar cezy Data 17 martie 2011 09:40:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#include<vector>
using namespace std;
#define NMAX 200005
int n,m,l=0;
vector <int> v[NMAX];
int g[NMAX],viz[NMAX],s[NMAX];
void citire ()
{
	ifstream fin("dfs.in");
	fin>>n>>m;
	int i,a,b;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(i=1;i<=n;i++)
		g[i]=v[i].size();
	fin.close();
}
void dfs(int nod)
{
	int i;
	viz[nod]=1;
	for(i=0;i<g[nod];i++)
		if(!viz[v[nod][i]])
		{
			dfs(v[nod][i]);
		}
}
int main ()
{
	int i,k=0;
	citire();
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			dfs(i);
			k++;
		}
	}
	ofstream fout("dfs.out");
	fout<<k;
	fout.close();
	return 0;
}