Cod sursa(job #551390)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 10 martie 2011 18:41:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<vector>
using namespace std;

const int NMAX=100000;
int viz[NMAX]={0};

void dfs2(const int&, const vector<int> *);

void dfs1(const vector<int> *v, int& numara, const int& noduri)
{
	numara=0;

	for(int i=0;i<noduri;i++)
	{
		if(!viz[i])
		{
			++numara;
			dfs2(i,v);
		}
	}
}

void dfs2(const int& rad, const vector<int> *v)
{
	viz[rad]=1;
	for(int i=0;i<(int) v[rad].size();i++)
	{
		if(!viz[v[rad][i]])
			dfs2(v[rad][i],v);
	}
}

int main()
{
	int n,m;
	vector<int> v[NMAX];

	ifstream in("dfs.in");
	ofstream out("dfs.out");
	in>>n>>m;

	int a,b,contor=0;
	for(int i=0;i<m;i++)
	{
		in>>a>>b;
		--a,--b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs1(v,contor,n);
	out<<contor<<"\n";
}