Cod sursa(job #1458235)

Utilizator glbglGeorgiana bgl glbgl Data 7 iulie 2015 10:26:45
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#include <vector>
#include <fstream>
#include <iostream>

#define MAX 100000

using namespace std;


int N, M, count = 0;
vector<int> tpl[MAX+1];
vector<int> c(MAX+1);

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



void read(){

	in >> N >> M;

	int x, y;

	for(int i = 0; i < M; ++i){
		in >> x >> y;
		tpl[x].push_back(y);
	}
}

void explorare(int u){

	c[u] = 1;
	for(unsigned int i = 0; i < tpl[u].size(); ++i){
		int v = tpl[u][i];
		if(c[v] == 0)
			explorare(v);
	}
	c[u] = 2;
}


void DFS(){

	for(int i = 1; i <= N; ++i){
		if(c[i] == 0){
			explorare(i);
			count++;
		}
	}
}


int main(){

	read();

	DFS();

	out << count;
}