Cod sursa(job #2796529)

Utilizator bianca_voicuBianca Voicu bianca_voicu Data 8 noiembrie 2021 13:09:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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


class Graph {
private:
    int _n, _m;
    vector<int> _list[100001];

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    vector<vector<int>> c_bic();

    void biconexe(int node, int parent, stack<int> &s, vector<int> &level, vector<int> &back, vector<vector<int>> &bic);
};


void
Graph::biconexe(int node, int parent, stack<int> &s, vector<int> &level, vector<int> &back, vector<vector<int>> &bic) {
    //calculez nivelurile nodurilor
    level[node] = level[parent] + 1;
    back[node] = level[node];

    s.push(node);
    //parcurg vecinii
    for (int i = 0; i < _list[node].size(); i++) {
        if (level[_list[node][i]]) {
            if (_list[node][i] != parent)
                //actualizez minimul
                back[node] = min(level[_list[node][i]], back[node]);
        } else {
            biconexe(_list[node][i], node, s, level, back, bic);  //dfs pentru biconexe
            back[node] = min(back[_list[node][i]], back[node]);
            if (level[node] <= back[_list[node][i]]) { //verific daca face parte din componenta biconexa
                vector<int> v;

                while (s.top() != _list[node][i]) {
                    v.push_back(s.top()); //pun in v elementele componentei biconexe
                    s.pop();
                }

                v.push_back(_list[node][i]);
                s.pop();
                v.push_back(node);

                bic.push_back(v);
            }
        }
    }
}

vector<vector<int>> Graph::c_bic() {
    vector<vector<int>> bic;

    //initializez cu 0 vectorii pentru nivel si pentru intoarcere
    vector<int> level(_n + 1, 0);
    vector<int> back(_n + 1, 0);
    stack<int> s;

    for (int i = 1; i <= _n; i++) {
        //pentru fiecare nod, in functia biconexe incep sa calculez nivelul daca acesta nu este inca setat
        if (!level[i]) {
            biconexe(i, 0, s, level, back, bic);
            //golesc stiva
            while (!s.empty()) {
                s.pop();
            }
        }
    }

    return bic;
}

void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; i++) {
        f >> x >> y;
        _list[x].push_back(y);
        _list[y].push_back(x);
    }
}


int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.addEdges();

    vector<vector<int>> bic = gr.c_bic();

    g << bic.size() << '\n';

    for (int i = 0; i < bic.size(); i++) {
        for (int j = 0; j < bic[i].size(); j++)
            g << bic[i][j] << " ";
        g << '\n';
    }

    f.close();
    g.close();
    return 0;
}