Cod sursa(job #505632)

Utilizator rares192Preda Rares Mihai rares192 Data 3 decembrie 2010 12:37:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream>
#include<vector>
#include<bitset>
#include<deque>
#include<list>
using namespace std;

ofstream fout("dfs.out");

void read();
void write();
void DF(int );
void ComponenteConexe();
void BF(int );
//void Push(int );
//void Pop(int );


int n, nr, m;
vector<vector<int> > a;
deque<int > Q; 
bool s[100001];
/*
struct NOD
		{
		int x;
		NOD *prim, *ultim;
		};
*/
int main()
{
	read();
	ComponenteConexe();
	fout << nr;
	return 0;
}

void read()
{
	ifstream fin("dfs.in");
	int i, j;
	fin >> n >> m;
	a.resize(n+1);
	
	while( fin >> i >> j)
	{
		a[i].push_back(j);
		a[j].push_back(i);
	}
	
    fin.close();
}

void DF(int x)
{
	int j;
	s[x] = 1;
	//fout << x << " ";
	for(int i = 0; i < (int)a[x].size(); ++i)
	{
		j = a[x][i];
		if(!s[j])
		{
			s[j] = 1;
			DF(j); 
		//	BF(j);
		}

	}
}

void ComponenteConexe()
{
	for(int i = 1; i <= n; i++)
		if( !s[i] )
		{
			nr++;
			s[i] = 1;
		//	fout << "componenta nr " << nr << ": ";
			DF(i);
		//	fout << endl;
		}
}

void BF(int x)
{
	s[x] = true;
	Q.push_back(x);
	fout << x << " ";
	
	while( !Q.empty() )
	{
		for(int i = 0 ; i < (int)a[x].size(); ++i)
			{
				int j;
				j = Q.front();
				Q.pop_front();
				if( !s[ a[x][i] ] )
				{
					Q.push_back(a[x][i]);
					s [ a[x][i] ] = true;
					fout << a[x][i] << " ";
				}
			}
	}
}