Cod sursa(job #1698726)

Utilizator Gabiap2015Apostol Gabriel Gabiap2015 Data 5 mai 2016 10:25:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int n, m;
vector< vector<int> >graph;
vector<bool> visited;
ifstream f("dfs.in");
ofstream g("dfs.out");
void dfs(int vertex)
{
	if (vertex<0 || vertex >= n) return;
	stack<int> s;
	int element, i;
	bool found;
	s.push(vertex);
	visited[vertex] = true;
	while (!s.empty())
	{
		element = s.top();
		found = false;
		for (i = 0; i<graph[element].size() && !found; i++)
		{
			if (!visited[graph[element][i]]) found = true;
		}
		if (found)
		{
			i--;
			s.push(graph[element][i]);
			visited[graph[element][i]] = true;
		}
		else s.pop();
	}
}
int main()
{
	int x, y, counter = 0;
	f >> n >> m;
	graph.resize(n);
	visited.resize(n, false);
	for (int i = 0; i<m; i++)
	{
		f >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	for (int i = 0; i<visited.size(); i++)
	if (!visited[i])
	{
		dfs(i);
		counter++;
	}
	g << counter << " ";
	return 0;
}