Cod sursa(job #3217926)

Utilizator BoggiGurau Bogdan Boggi Data 25 martie 2024 10:44:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

#define VI vector<int>
#define VB vector<bool>
#define VVI vector<VI>
#define pb push_back

int N, M;
VVI adList;
VB vis;

void DFS(int nod);

int main() { 
    fin >> N >> M;
    adList = VVI(N + 1);
    vis = VB(N + 1, false);
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        adList[x].pb(y);
        adList[y].pb(x);
    }

    int nrComp = 0;
    for (int nod = 1; nod <= N; ++nod) {
        if (!vis[nod]) {
            ++nrComp;
            vis[nod] = true;
            DFS(nod);
        }
    }
    fout << nrComp;
}

void DFS(int nod) {
    for (auto vecin : adList[nod]) {
        if (!vis[vecin]) {
            vis[vecin] = true;
            DFS(vecin);
        }
    }
}