Cod sursa(job #2740647)

Utilizator SerbaP123Popescu Serban SerbaP123 Data 13 aprilie 2021 18:18:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <map>
#include <vector>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

const int nmax = 1e5;

int N, M, componente_conexe, x, y;
vector <int> muchii[nmax + 1];
bool vizitat[nmax + 1];

void DFS(int nod){
    vizitat[nod] = true;
    for(int i = 0; i < muchii[nod].size(); ++i){
        if(!vizitat[muchii[nod][i]]){
            DFS(muchii[nod][i]);
        }
    }
}

int main(){
    cin >> N >> M;
    while(M--){
        cin >> x >> y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    for(int i = 1; i <= N; ++i){
        if(!vizitat[i]){
            componente_conexe++;
            DFS(i);
        }
    }
    cout << componente_conexe;
    return 0;
}