Cod sursa(job #1044785)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 30 noiembrie 2013 13:12:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

struct node
{
	vector<int> vecini;
	bool vizitat = false;
};

void dfs(node* noduri, int i)
{

	stack<node*> stiva;
	stiva.push(&noduri[i]);

	while (stiva.empty() == false)
	{
		node* top = stiva.top();
		stiva.pop();
		top->vizitat = true;


		for (vector<int>::const_iterator it = top->vecini.begin(); it != top->vecini.end(); it++)
		{
			if (noduri[*it].vizitat == false)
				stiva.push(&noduri[*it]);
		}
	}


}

int main()
{
	ifstream IN("dfs.in");
	ofstream OUT("dfs.out");

	node *noduri;
	int n, m;
	int componenteCon = 0;

	IN >> n >> m;

	noduri = new node[n + 1];

	for (int i = 0; i < m; i++)
	{
		int x, y; IN >> x >> y;

		noduri[x].vecini.push_back(y);
		noduri[y].vecini.push_back(x);
	}

	for (int i = 1; i <= n; i++)
	{
		if (noduri[i].vizitat == false)
			dfs(noduri, i), ++componenteCon;
	}

	delete[] noduri;

	OUT << componenteCon << "\n";

	return 0;
}