Cod sursa(job #3160183)

Utilizator AlexandraTomaToma Alexandra AlexandraToma Data 23 octombrie 2023 11:08:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

//declarari globale
const int NMAX = 100000;
int vis[NMAX + 1] = {0}; //vector vizitate
vector <int> G[NMAX + 1]; //vector de vectori = lista de adiacenta

void DFS(int x) {
    //vizitam nodul
    vis[x] = 1;
    //cautam vecinii
    for(auto next: G[x]) {
        //daca inca nu am vizitat vecinul next
        if(!vis[next]) {
            //marcam ca vizitat
            vis[next] = 1;
            //continuam parcurgerea
            DFS(next);
        }
    }
}

int main() {

    //fisiere I/O
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    //citim graful
    int N, M;
    f >> N >> M;
    for (int i = 1; i <= M ; ++i) {
        int a, b;
        f >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    //numarul de componente conexe
    int nr = 0;
    //pentru fiecare varf nevizitat aplicam DFS, fiecare DFS oarcurge o noua componenta conexa
    for(int i = 1; i <= N; i++)
        if(vis[i] == 0) {
            nr++;
            DFS(i);
        }

    //afisam nr componente
    g << nr;

    f.close();
    g.close();
    return 0;
}