Cod sursa(job #2783456)

Utilizator StarkillerCalin Stafie Starkiller Data 14 octombrie 2021 15:01:13
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

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

class Graful_meu
{
    int _noduri;
    int _muchii;
    vector<vector<int>> lista_muchii;
    //bool noduri_vizitate[NMAX]; -- in fiecare metoda care are nevoie de el (NU AICI)

public:
    Graful_meu();   // daca ni se da lista de adiacenta
    int Componente_conexe();
    void citire_muchii();
    void DFS(int start, vector<bool> &vizitat);
    void BFS();
};
Graful_meu::Graful_meu()
{
    _noduri = 0;
    _muchii = 0;
}
void Graful_meu::citire_muchii()
{
    int x, y;
    fin >> _noduri;
    fin >> _muchii;
    lista_muchii.resize(_noduri+2);
    for(int i = 0 ; i < _noduri ; ++i)
    {
        fin >> x >> y;
        lista_muchii[x].push_back(y);
        lista_muchii[y].push_back(x);
    }
}
void Graful_meu::DFS(int start, vector<bool> &vizitat)
{
    vizitat[start] = 1;
    for(int &nod_vecin : lista_muchii[start])
        if(vizitat[nod_vecin] == 0)
            DFS(nod_vecin, vizitat);

}
int Graful_meu::Componente_conexe()
{
    vector <bool> vizitat(_noduri + 2);
    int numar_componente_conexe = 0;
    for(int i = 0 ; i < _noduri ; ++i)
        if (vizitat[i] == 0)
        {
            DFS(i, vizitat);
            ++numar_componente_conexe;
        }
    return numar_componente_conexe;
}
int main()
{
    Graful_meu g;
    g.citire_muchii();
    gout << g.Componente_conexe();
    return 0;
}