Cod sursa(job #1682166)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 9 aprilie 2016 23:53:29
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>

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


int NrNoduri, NrMuchii, x, y, compConex;

vector<int> vecini[100001];
bool visit[100001];

void BFS(int x) {
    visit[x] = 1;

    for ( vector<int>::iterator it = vecini[x].begin() ; it!=vecini[x].end() ; it++ )
        BFS(*it);
}

int main() {
    f >> NrNoduri >> NrMuchii;

    for ( int i=1 ; i<=NrMuchii ; i++ ) {
        f >> x >> y;

        vecini[x].push_back(y);
    }

    for ( int i=1 ; i<=NrNoduri ; i++ )
        if ( !visit[i] ) {
            BFS(i);
            compConex++;
        }
    g << compConex;
}