Cod sursa(job #1248492)

Utilizator silidragosSilion Dragos silidragos Data 25 octombrie 2014 12:43:31
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 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){
	stack<int> stiva;

	stiva.push(k);

	int aux;
	while (!stiva.empty()){
		aux = stiva.top();
		stiva.pop();
		for (int i = 0; i < L[aux].size(); i++){
			if (C[L[aux][i]] == 0){
				C[L[aux][i]] = 1;
				stiva.push(L[aux][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);

	}
	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;
}