Cod sursa(job #2653620)

Utilizator raikadoCri Lu raikado Data 28 septembrie 2020 17:22:43
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

uint dfs(vector<vector<uint>> &edges)
{
	size_t N = edges.size();
	vector<bool> visited(N, false);

	stack<uint> S;
	uint comps = 0;

	for (size_t i = 0; i < N; i++)
	{
		if (!visited[i])
		{
			S.push(i);
			comps++;
			while (!S.empty())
			{
				uint v = S.top();
				S.pop();

				if (!visited[v])
				{
					visited[v] = true;

					for (uint w : edges[v])
					{
						S.push(w);
					}
				}
			}
		}
	}

	return comps;
}

int main(int argc, char const *argv[])
{
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");

	uint N, M;
	fin >> N >> M;

	vector<vector<uint>> edges(N);
	for (uint i = 0; i < M; i++)
	{
		uint x, y;
		fin >> x >> y;
		edges[x-1].push_back(y-1);
	}

	fout << dfs(edges);


	return 0;
}