Cod sursa(job #771669)

Utilizator harababurelPuscas Sergiu harababurel Data 26 iulie 2012 19:56:04
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100001
using namespace std;

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

vector <int> vecin[nmax];
stack <int> st;
bool vizitat[nmax];
int top;

void dfs(int curent) {
	st.push(curent);
	vizitat[curent] = true;
	//g<<curent<<" ";
	
	for(int i = 0; i < vecin[curent].size(); i++) {
		dfs(vecin[curent][i]);
	}
	
	//vizitat[curent] = false;
}
	
	

int main() {
	int n, m, i, j, a, b, rez=0;
	
	f>>n>>m;
	
	for(i=1; i<=m; i++) {
		f>>a>>b;
		vecin[a].push_back(b);
	}
	
	for(i=1; i<=n; i++) {
		if(!vizitat[i]) {	
			rez++;
			dfs(i);
		}
	}
	
	g<<rez<<"\n";
	
	f.close();
	g.close();
	return 0;
}