Cod sursa(job #2423593)

Utilizator AndreiAsAndrei Sugeac AndreiAs Data 21 mai 2019 18:36:53
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 10001
using namespace std;

int N, M;
vector <int> lista[nmax];
int vizitate[nmax];
int comp = 0;

void DFS(int nod)
{
	vizitate[nod] = 1;
	if (lista[nod].empty()) return;
	for (int i : lista[nod])
		if (vizitate[i] == 0) DFS(i);
}

int main()
{
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	f >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int x, y;
		f >> x >> y;
		lista[x].push_back(y);
	}

	for (int i = 1; i <= N; ++i) {
		if (vizitate[i] == 0) {
			DFS(i);
			comp++;
		}
	}
	g << comp;
	return 0;
}