Cod sursa(job #2660328)

Utilizator Zamfirescuste2Zamfirescu Stefan Zamfirescuste2 Data 18 octombrie 2020 21:46:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <iostream>
#include <vector>

const int MAXNOD = 1e5 + 1;

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

std :: vector <int> lists[MAXNOD];
std :: vector <int> viz (MAXNOD);

void DFS(int nod);

int main (){
    int n,m;

    f >> n >> m;
    for (int index = 0; index < m; index ++ ){
        int x, y;
        f >> x >> y;
        lists[x].push_back(y);
        lists[y].push_back(x);
    }

    int compConexe = 0;
    for (int elem = 1; elem <= n; elem++){
        if (viz[elem] == 0){
            DFS(elem);
            compConexe++;
        }
    }
    
    g << compConexe << "\n";
}

void DFS (int nod){
    viz[nod] = 1;
    for (int elem : lists[nod])
        if (!viz[elem])
            DFS(elem);
}