Cod sursa(job #2475757)

Utilizator mihneazarojanuMihnea Bogdan Zarojanu mihneazarojanu Data 17 octombrie 2019 15:58:46
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>

using namespace std;

const int VM = 100001;

bool viz[VM];
int vf[2 * VM], urm[2 * VM], lst[VM], nr;

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

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

int main(){
    int n, m, nr = 0;
    ifstream in("dfs.in");
    in >> n >> m;
    for(int i = 0; i < n; i++){
        int x, y;
        in >> x >> y;
        adaugare(x, y);
        adaugare(y, x);
    }
    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            nr++;
        }
        dfs(i);
    }
    ofstream out("dfs.out");
    out << nr;
    out.close();
    return 0;
}