Cod sursa(job #966821)

Utilizator BlackElfSpulber Iosif BlackElf Data 26 iunie 2013 16:49:47
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int N, M;

vector <vector <int>> graph;
vector <bool> visited;

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

void load ()
{
	in >> N >> M;
	
	graph.resize(N);
	visited.resize(N, false);
	
	for (int i = 0; i < M; i++)
	{
		int a, b;
		in >> a >> b;
		
		graph[a-1].push_back (b-1);
	}
}

void dfs (int start)
{
	stack<int> st;
	st.push (start);
	
	visited[start] = true;
	
	while (!st.empty())
	{
		int node = st.top();
		st.pop();
		
		for (int i = 0; i < graph[node].size(); i++)
		{
			visited[graph[node][i]] = true;
			st.push(graph[node][i]);
		}
	}
}

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

int main ()
{
	load ();

	out << countConexComp () << endl;
	
	return 0;
}