Cod sursa(job #2796210)

Utilizator AndreeaGeamanuAndreea AndreeaGeamanu Data 7 noiembrie 2021 18:46:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

#define nmax 100010

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

vector <int> la[nmax];
int viz[nmax]={0}, conex=0;

void DFS(int nod){

    // Se marcheaza nodul curent ca fiind vizitat
    viz[nod]=1;
    // Se viziteaza toate nodurile la care poate ajunge nodul curent,
    // apelandu-se recursiv functia DFS
    for(int j=0; j<la[nod].size(); j++){
        if(viz[la[nod][j]]==0)
            DFS(la[nod][j]);
    }
}


int main()
{   int n,m,x,y;

    f>>n>>m;

    //Se introduc muchiile in liste de adiacenta
    for(int i=1; i<=m; i++){
        f>>x>>y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    for(int j=1; j<=n; j++){
        // Pentru fiecare nod nevizitat se marcheaza toate nodurile
        // componentei conexe din care face parte apelandu-se functia DFS
        if(viz[j]==0){
            conex++;
            DFS(j);
        }
    }

    g<<conex;

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