Cod sursa(job #2448292)

Utilizator red_devil99Mancunian Red red_devil99 Data 16 august 2019 15:29:55
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.5 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int N, M;
int vizat[100010];
std::vector<int> v[100010];
int nr  = 0;

void dfs(int nod){
	vizat[nod] = 1;
	for(auto it : v[nod]){
		if(!vizat[it]){
			dfs(it);
		}
	}
}

int main(){
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	fin >> N >> M;
	int x, y;
	for(int i = 1; i <= M; i++){
		fin >> x >> y;
		v[x].push_back(y);
	}
	for(int i = 1; i <= N; i++){
		if(!vizat[i]){
			dfs(i);
			nr++;
		}
	}
	fout << nr;
	return 0;
}