Cod sursa(job #3156655)

Utilizator Yanis3PiquePopescu Pavel-Yanis Yanis3Pique Data 12 octombrie 2023 00:42:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

void DFS(int x, vector <int> G[], int vis[]) {
    vis[x] = 1;
    for(auto next : G[x]) {
        if(vis[next] == 0) DFS(next, G, vis);
    }
}

int main() {
    const int NMAX = 100000;
    int N, M, nr_componente_conexe = 0, vis[NMAX + 1] = {0};
    f >> N >> M;
    vector <int> G[N + 1];
    for(int i = 1; i <= M; i++) {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int j = 1; j <= N; j++) {
        if(vis[j] == 0) {
            nr_componente_conexe++;
            DFS(j, G, vis);
        }
    }
    g << nr_componente_conexe;
}