Cod sursa(job #2764382)

Utilizator DariusMDarius Feher DariusM Data 20 iulie 2021 18:01:25
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

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

const int maxVert = 100001;

vector<int> Adj[maxVert];
stack<int> nodes;
bool visited[maxVert];

void dfs(int source) {
	visited[source] = true;
	nodes.push(source);
	int top;
	while (!nodes.empty()) {
		top = nodes.top();
		nodes.pop();
		int n = Adj[top].size();
		for (int i = 0; i < n; ++i) {
			if (!visited[Adj[top][i]]) {
				visited[Adj[top][i]] = true;
				nodes.push(Adj[top][i]);
			}
		}
	}
}

int main() {
	int n, m, s, x, y;
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		f >> x >> y;
		Adj[x].push_back(y);
	}
	int no_comp = 0;
	for (int i = 1; i <= n; ++i) {
		if (!visited[i]) {
			++no_comp;
			dfs(i);
		}
	}
	g << no_comp;
	f.close();
	g.close();
	return 0;
}