Cod sursa(job #1430445)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 8 mai 2015 14:30:41
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>

#define NMax 100010

using namespace std;

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

vector<int> G[NMax];
int nodes, edges, conxcom, n1, n2, top;
bool mark[NMax];

struct mstack
{
	int node;
	int indx;
}st[NMax];

void dfs(int stnode) {

	st[++top].node = stnode;
	st[top].indx = 0;
	mark[stnode] = 1;

	while (top > 0) {
		while (st[top].indx == G[st[top].node].size() && top > 0)
			top--;

		if (top == 0)
			break;

		if (!mark[G[st[top].node][st[top].indx]]) {
			st[++top].node = G[st[top - 1].node][st[top - 1].indx];
			st[top].indx = 0;
			mark[st[top].node] = 1;

			st[top - 1].indx++;
		}
		else
			st[top].indx++;

	}

}

int main()
{
	f >> nodes >> edges;

	for (int i = 1; i <= nodes; i++) {
		f >> n1 >> n2;

		G[n1].push_back(n2);
		G[n2].push_back(n1);
	}

	for (int i = 1; i <= nodes; i++) {
		if (!mark[i]) {
			top = 0;
			conxcom++;
			dfs(i);
		}
	}

	g << conxcom;

	return 0;
}