Cod sursa(job #2501970)

Utilizator kodama cheama alex koda Data 30 noiembrie 2019 12:15:54
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>

using namespace std;

const int N = 100001;
const int M = 2*N*(N-1);
int lst[N], vf[2*M], urm[2*M], n, nr;
bool viz[N], nv;

void adauga (int x, int y) {
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs ( int x ) {
    viz[x] = true;
    for ( int p = lst[x]; p != 0; p = urm[p] ) {
        int y = vf[p];
        if ( !viz[y] )
            dfs(y);
    }
}

int main () {
    ifstream fin ("dfs.in");
    ofstream fout ("dfs.out");
    int m, gcon = 0, x, y;
    fin>>n>>m;
    for ( int i = 0; i < m; i++ ) {
        fin>>x>>y;
        adauga(x,y);
    }
    for ( int i = 1; i <= n; i++ ) {
        if ( viz[i] == false ) {
            gcon++;
            dfs(i);
        }
    }
    fout<<gcon;
    return 0;
}