Cod sursa(job #764423)

Utilizator mi5humihai draghici mi5hu Data 5 iulie 2012 11:22:49
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <fstream>
#include <vector>
using namespace std;

vector<int> edges[100020];
bool vazut[100020];
int n, m;

void citeste() {
    int sursa, dest;     
    ifstream f("dfs.in");
    
    f >> n >> m;
    for (int i = 0; i < m; i++) {
        f >> sursa >> dest;
        edges[sursa].push_back(dest);
    }
    
    f.close();     
}

void dfs(int el) {
    vazut[el] = true;
    vector<int>::iterator it;
    for (it = edges[el].begin(); it != edges[el].end(); it++) {
        if (!vazut[*it]) {
             dfs(*it); 
        }
    }      
}

int comp_conexe() {
    int cc = 0;
    for (int i = 1; i <= n; i++) {
        if (!vazut[i]) {
           cc++;
           dfs(i);               
        }
    }     
    return cc;
}

void afiseaza(int cc) {     
    ofstream g("dfs.out");    
    g << cc;    
    g.close();
}

int main() {
    
    citeste();
    int cc = comp_conexe();
    afiseaza(cc);    
    
    return 0;
}