Cod sursa(job #440922)

Utilizator darrenRares Buhai darren Data 12 aprilie 2010 17:45:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#include<vector>
using namespace std;

void read();
void doit();
void dfs( int x );
void write();

int n, m;
vector<vector<int> > mat(100005);
vector<bool> selected(100005);
int conex;

int main()
{
	read();
	doit();
	write();
	return 0;
}

void read()
{
	ifstream fin( "dfs.in" );
	fin >> n >> m;
	for ( int i = 0; i < m; ++i )
	{
		int x, y;
		fin >> x >> y;
		mat[x].push_back(y);
		mat[y].push_back(x);
	}
	fin.close();
}

void doit()
{
	for ( int i = 1; i <= n; ++ i )
		if ( !selected[i] )
		{
			dfs(i);
			++conex;
		}
}

void dfs( int x )
{
	for ( vector<int>::iterator i = mat[x].begin(); i < mat[x].end(); ++i )
		if ( !selected[*i] )
		{
			selected[*i] = true;
			dfs(*i);
		}
}

void write()
{
	ofstream fout( "dfs.out" );
	fout << conex;
	fout.close();
}