Cod sursa(job #3249422)

Utilizator PuckaaaCuclea Luca Puckaaa Data 16 octombrie 2024 11:07:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
#include <vector>
using namespace std;

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

void memorareLiAd(vector<vector<int> >& liAd, int nrNoduri, int nrMuchii, bool orientat)
{
    for (int i = 0; i < nrMuchii; i++)
    {
        int x, y;
        f >> x >> y;
        liAd[x].push_back(y);
        if (!orientat)
            liAd[y].push_back(x);
    }
}

void DFS(vector<vector<int> >& liAd, int nodCurent, vector<bool>& vizitat)
{
    // daca nu punem static, vectorul va fi initializat de fiecare data cand se apeleaza functia recursiv
    vizitat[nodCurent] = true; // marcam nodul curent ca vizitat
    //cout << nodCurent << " ";
    for (int i = 0; i < liAd[nodCurent].size(); i++) // parcurgem vecinii nodului curent
        if (!vizitat[liAd[nodCurent][i]]) // daca vecinul nu a fost vizitat, apelam recursiv DFS
            DFS(liAd, liAd[nodCurent][i], vizitat);
}

int numarCompConexe(vector<vector<int> >& liAd)
{
    int nrCompConexe = 0;
    vector<bool> vizitat(liAd.size(), false); // vectorul de vizitat
    for (int i = 1; i < liAd.size(); i++) // parcurgem toate nodurile
        if (!vizitat[i]) // daca nodul nu a fost vizitat, apelam DFS
        {
            nrCompConexe++; // incrementam numarul de componente conexe
            DFS(liAd, i, vizitat); // apelam DFS care va marca toate nodurile din componenta conexa
        }
    return nrCompConexe;
}

int main()
{
    int nrNoduri, nrMuchii;
    f >> nrNoduri >> nrMuchii;
    vector<vector<int> > liAd(nrNoduri + 1);
    vector<bool> vizitat(nrNoduri + 1, false);
    memorareLiAd(liAd, nrNoduri, nrMuchii, false);
    g<<numarCompConexe(liAd);
    f.close();
    g.close();
    return 0;
}