Cod sursa(job #1248497)

Utilizator silidragosSilion Dragos silidragos Data 25 octombrie 2014 12:48:39
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>

#define nmax 100001
using namespace std;

vector<int> L[nmax];
int C[nmax];
void DFS(int k){
	
	for (int i = 0; i < L[k].size(); i++){
		if (C[L[k][i]] == 0){
			C[L[k][i]] = 1;
			DFS(L[k][i]);
		}
	}

}

int main(){
	ifstream f("dfs.in", ios::in);
	ofstream g("dfs.out", ios::out);

	int N, M;
	f >> N >> M;

	for (int i = 0; i < M; ++i){
		int x, y;
		f >> x >> y;
		L[x].push_back(y);

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

	g << comp << endl;

	f.close();
	g.close();
	return 0;
}