Cod sursa(job #2636935)

Utilizator Snake2003lalallalal Snake2003 Data 20 iulie 2020 17:50:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>

#define Nmax 100005

using namespace std;

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

int nr_varfuri, nr_muchii;
int componente_conexe;

vector < int > Numere[Nmax];

bool Vizitat[Nmax];

void DFS(int Nod)
{
    Vizitat[Nod] = true;
    for(unsigned int i = 0; i < Numere[Nod].size(); i ++)
    {
        int Vecin = Numere[Nod][i];
        if(!Vizitat[Vecin])
            DFS(Vecin);
    }
}

int Read()
{
    fin >> nr_varfuri >> nr_muchii;
    for(int i = 1; i <= nr_muchii; i ++)
    {
        int x, y;
        fin >> x >> y;
        //stocam componentele conexe dus - intors pentru ca avem graf neorientat
        Numere[x].push_back(y);
        Numere[y].push_back(x);
    }
    /*
    * 1: 2 4
    * 2: 1
    * 3: 5
    * 4: 1
    * 5: 3
    * 6: -
    */
    for(int i = 1; i <= nr_varfuri; i ++)
    {
        if(!Vizitat[i])
        {
            componente_conexe ++;
            DFS(i);
        }
    }
    fout << componente_conexe;
}

int main()
{
    Read();
    return 0;
}