Cod sursa(job #475838)

Utilizator ilie.danilaIlie Teodor Danila ilie.danila Data 8 august 2010 19:37:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>

using namespace std;

struct node
{
	int value;
	vector<node*> neighbors;
};

int n, m, i, x, y;
int sel[100001];
int compConex;
vector<node*> nodes;

void dfs( node* aNode );

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

	f >> n >> m;

	for( i = 0; i < n; i++ )
	{
		node* newNode = new node;
		newNode->value = i;
		nodes.push_back( newNode );
	}

	for( i = 0; i < m; i++ )
	{
		f >> x >> y;
		x--;
		y--;
		nodes[x]->neighbors.push_back( nodes[y] );
		nodes[y]->neighbors.push_back( nodes[x] );
	}

	f.close();

	for( i = 0; i < n; i++ )
	{
		if( !sel[i] )
		{
			compConex++;
			dfs( nodes[i] );
		}
	}

	g << compConex << "\n";

	g.close();

	return 0;
}

void dfs( node* aNode )
{
	sel[aNode->value] = 1;
	for( int ind = 0; ind < aNode->neighbors.size(); ind++ )
	{
		if( !sel[aNode->neighbors[ind]->value] )
		{
			dfs( aNode->neighbors[ind] );
		}
	}
}