Cod sursa(job #3272208)

Utilizator AndreiLeusteanLeustean Andrei AndreiLeustean Data 28 ianuarie 2025 21:00:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.71 kb
#include <bits/stdc++.h>

using namespace std;

// ifstream in("citire.in");
ifstream in("dfs.in");
ofstream out("dfs.out");
const int infinity = numeric_limits<int>::max();
const int infinitytMin = numeric_limits<int>::min();

// muchie de la x la y cu costul cost
struct Muchie
{
    int x, y;
    int cost = 0;
    int capacitate = -1;
    int flux = -1;

    Muchie() = default;

    Muchie(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }

    Muchie(int x, int y)
    {
        this->x = x;
        this->y = y;
    }

    Muchie(int x, int y, int flux, int capacitate)
    {
        this->x = x;
        this->y = y;
        this->flux = flux;
        this->capacitate = capacitate;
    }
};

bool comparison(Muchie m1, Muchie m2)
{
    return m1.cost < m2.cost;
}

struct Nod
{
    int nod;
    int cost = 0;
    int capacitate = -1;
    int flux = -1;

    Nod() = default;
    Nod(int nod) { this->nod = nod; }
    Nod(int nod, int cost)
    {
        this->nod = nod;
        this->cost = cost;
    }

    Nod(int nod, int flux, int capacitate)
    {
        this->nod = nod;
        this->flux = flux;
        this->capacitate = capacitate;
    }

    bool operator<(const Nod &obj) const
    {
        return this->cost > obj.cost; //> pt min-heap
    }
};

// vector<Muchie> dfsMuchii;

class Graf
{
public:
    int nrNoduri;
    int nrMuchii;
    vector<bool> vizitat;
    vector<int> grad_intern;
    vector<int> grad_extern;
    vector<vector<Nod>> lista_adiacenta;
    vector<Muchie> muchii;

    Graf() = default;

    Graf(int nrNoduri)
    {
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    Graf(int nrNoduri, int nrMuchii)
    {
        this->nrMuchii = nrMuchii;
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1, false);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }

    void iterativeDFS(int start, vector<int> &tati)
    {
        int n = nrNoduri;
        stack<int> stack;
        stack.push(start);

        while (!stack.empty())
        {
            int nod = stack.top();
            stack.pop();

            if (vizitat[nod] == false)
            {
                // cout << nod;
                vizitat[nod] = true;
            }

            for (auto vecin : lista_adiacenta[nod])
                if (vizitat[vecin.nod] == false)
                {
                    // dfsMuchii.push_back(Muchie(nod, vecin.nod));
                    stack.push(vecin.nod);
                }
            // else if (tati[vecin.nod] != nod)
            //     return false;
        }
        // return true;
    }

    void printGraf()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": ";
            for (auto nod : lista_adiacenta[i])
                cout << nod.nod << "(" << nod.cost << ") ";
            cout << endl;
        }
    }
};

int main()
{
    int n, m;
    in >> n >> m;
    Graf g(n, m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        g.lista_adiacenta[x].push_back(Nod(y));
        g.lista_adiacenta[y].push_back(Nod(x));
    }
    vector<int> tata(n + 1);
    int nr = 0;
    for (int i = 1; i <= n; i++)
    {
        if (g.vizitat[i] == false)
        {
            nr++;
            g.iterativeDFS(i, tata);
        }
    }
    cout << nr;
    return 0;
}