Cod sursa(job #1539595)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 1 decembrie 2015 01:01:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
// infoarenaDFSnonRec.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <vector>
#include <fstream>
#include <stack>
#include <assert.h>

#define MaxN 100005

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N, M,x, y;
vector<int> G[MaxN];
bool visited[MaxN];
int neighIndexes[MaxN];
stack<int> mystack;

void dfs(int src) {
	visited[src] = true;
	mystack.push(src);

	while (!mystack.empty()) {
		assert(mystack.size() <= N);
		int node = mystack.top();

		while (neighIndexes[node] < G[node].size() && visited[G[node][neighIndexes[node]]])
			++neighIndexes[node];

		if (neighIndexes[node] != G[node].size()) {
			int next = G[node][neighIndexes[node]];

			visited[next] = true;
			mystack.push(next);
		}
		else {
			mystack.pop();
		}
	}
}

int main()
{
	fin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	int count = 0;
	for (int i = 1; i <= N; ++i) {
		if (!visited[i]) {
			dfs(i);
			++count;
		}
	}

	fout << count << '\n';

    return 0;
}