Cod sursa(job #3249900)

Utilizator andreidurdunDurdun Andrei andreidurdun Data 18 octombrie 2024 18:22:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;

class Graf
{
public:
    int N;
    bool orientat;
    vector<list<int>> listaAdiacenta;
    vector<bool> vizitat;

    int cateComponente=1;
    vector<int> componente; //componente[i] = in a cata componenta e nodul i

    Graf(int N, int orientat)
    {
        this->N = N;
        this->orientat = orientat;
        listaAdiacenta.resize(N + 1);
        vizitat.assign(N + 1, false);

        componente.resize(N+1);
    }

    // Adaugă o muchie între nodurile u și v
    void AdaugaMuchie(int u, int v) 
    {
        listaAdiacenta[u].push_back(v); // Adăugăm v în lista de adiacență a lui u
        if(orientat==1)
            listaAdiacenta[v].push_back(u); // Dacă graful este neorientat, adăugăm u în lista lui v
    }

    void AfisareListaAd()
    {
        for(int i=1; i<=N; i++)
            //if(!listaAdiacenta[i].empty()) //daca lista nodului i nu e vida, o afisez
            {
                cout<<i<<" : ";
                for(int nod : listaAdiacenta[i])
                    cout<<nod<<" ";
                cout<<endl;
            }
    }

    void DFS(int nod)
    {
        if(vizitat[nod]==true)
            return;
        
        vizitat[nod]=true;

        componente[nod]=cateComponente;
        
        for(int vecin : listaAdiacenta[nod])
            DFS(vecin);
    }

    void GasesteComponente()
    {
        for(int i=1; i<=N; i++)
            if(vizitat[i]==false)
            {
                cateComponente++;
                DFS(i);
            }
    }
};

ifstream f("dfs.in");
ofstream g("dfs.out");
int main()
{
    int N,M,u,v;
    f>>N>>M;
    Graf graf(N,1);

    for(int i=0; i<M; i++)
    {
        f>>u>>v;
        graf.AdaugaMuchie(u,v);
    }

//Numarul componentelor conexe ale garfului
    graf.DFS(1);
    graf.GasesteComponente();
    
    g<<graf.cateComponente;

    return 0;
}