Cod sursa(job #2795808)

Utilizator DenisTroacaDenis Troaca DenisTroaca Data 7 noiembrie 2021 00:16:38
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.93 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

class Graph
{
    int n;                      //nr de noduri
    int m;                      //nr de muchii
    vector<vector<int> > neighbors; //vector ce contine cate un vector cu vecini pt fiecare nod
    bool oriented;              // variabiabila pt a verifca daca e orientat
    bool from1;                 // variabila pt a verifica daca nodurile sunt numerotate de la 1
public:
    //constructori:
    Graph(int, bool, bool);
    Graph(int, int, bool, bool);

    void insert_edge(int, int); //functie pt a insera muchii

    vector<int> bfs(int); //functie pt a afla distantele minime de la un nod la celelate

    int connected_comp();          //functie pt a afla nr de componente conexe
    void dfs(int, vector<bool> &); //functie pt parcurgerea in adancime a unei componente

    vector<vector<int> > biconnected_comp();                                                            //functie pt a afla nr de componente biconexe
    void biconnected_dfs(int, int, vector<int> &, vector<int> &, stack<int> &, vector<vector<int> > &); //functie pt parcurgerea in adancime
};
Graph::Graph(int n, bool oriented = false, bool from1 = false)
{
    this->n = n;
    m = 0;
    this->from1 = from1;
    this->oriented = oriented;
    for (int i = 0; i < n; i++)
    {
        vector<int> aux;
        neighbors.push_back(aux);
    }
}
Graph::Graph(int n, int m, bool oriented = false, bool from1 = false)
{
    this->n = n;
    this->m = m;
    this->from1 = from1;
    this->oriented = oriented;
    for (int i = 0; i < n; i++)
    {
        vector<int> aux;
        neighbors.push_back(aux);
    }
}

void Graph::insert_edge(int x, int y)
{
    if (from1)
    {
        neighbors[x - 1].push_back(y - 1);
        if (!oriented)
            neighbors[y - 1].push_back(x - 1);
    }
    else
    {
        neighbors[x].push_back(y);
        if (!oriented)
            neighbors[y].push_back(x);
    }
}

vector<int> Graph::bfs(int x)
{
    vector<int> dist; //vector pt a memora distantele
    queue<int> aux;   //coada ce retine nodurile ce trebuie explorate
    for (int i = 0; i < n; i++)
        //nodurile nevizitate primesc distanta -1:
        dist.push_back(-1);
    if (from1)
        x--;
    aux.push(x);
    dist[x] = 0;
    while (!aux.empty())
    {
        for (int i = 0; i < neighbors[aux.front()].size(); i++)
        {
            //verificam daca nodurile vecine cu cel din varful cozii nu au fost vizitate:
            if (dist[neighbors[aux.front()][i]] == -1)
            {
                //retinem distanta:
                dist[neighbors[aux.front()][i]] = dist[aux.front()] + 1;
                //adaugam nodul vizitat in coada:
                aux.push(neighbors[aux.front()][i]);
            }
        }
        //trecem la urmatorul nod ce trebuie explorat:
        aux.pop();
    }
    return dist;
}

int Graph::connected_comp()
{
    int nr = 0;           //variabila pt a memora nr de componente conexe
    vector<bool> visited; // vector care verifica daca nodurile au fost vizitate
    for (int i = 0; i < n; i++)
        visited.push_back(false);
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == false)
        {
            nr++;
            //facem parcurgere in adancime pt a vizita toate nodurile componentei conexe:
            dfs(i, visited);
        }
    }
    return nr;
}
void Graph::dfs(int x, vector<bool> &visited)
{
    visited[x] = true;
    for (int i = 0; i < neighbors[x].size(); i++)
        if (visited[neighbors[x][i]] == false)
            dfs(neighbors[x][i], visited);
}

vector<vector<int> > Graph::biconnected_comp()
{
    vector<int> lvl;
    vector<int> min_lvl;
    stack<int> nodes;
    vector<vector<int> > components;

    for (int i = 0; i < n; i++)
    {
        lvl.push_back(-1);
        min_lvl.push_back(-1);
    }
    for (int i = 0; i < n; i++)
    {
        if (lvl[i] < 0)
        {
            biconnected_dfs(i, 0, lvl, min_lvl, nodes, components);
            if (!nodes.empty())
            {
                vector<int> aux;
                while (!nodes.empty())
                {
                    aux.push_back(nodes.top());
                    nodes.pop();
                }
                aux.push_back(i);
                components.push_back(aux);
            }
        }
    }
    return components;
}
void Graph::biconnected_dfs(int x, int current_lvl, vector<int> &lvl, vector<int> &min_lvl, stack<int> &nodes, vector<vector<int> > &components)
{
    lvl[x] = current_lvl;
    min_lvl[x] = current_lvl;
    int children = 0;
    for (int i = 0; i < neighbors[x].size(); i++)
    {
        if (lvl[neighbors[x][i]] < 0)
        {
            children++;
            nodes.push(neighbors[x][i]);
            biconnected_dfs(neighbors[x][i], current_lvl + 1, lvl, min_lvl, nodes, components);
            min_lvl[x] = min(min_lvl[x], min_lvl[neighbors[x][i]]);
            if ((lvl[x] == 0 && children > 1) || (lvl[x] > 0 && lvl[x] <= min_lvl[neighbors[x][i]]))
            {
                vector<int> aux;
                while (nodes.top() != neighbors[x][i])
                {
                    aux.push_back(nodes.top());
                    nodes.pop();
                }
                nodes.pop();
                aux.push_back(neighbors[x][i]);
                aux.push_back(x);
                components.push_back(aux);
            }
        }
        else
            min_lvl[x] = min(min_lvl[x], lvl[neighbors[x][i]]);
    }
}

int main()
{
    int n, m, a, b;
    fin >> n >> m;
    Graph g(n, m, false, true);
    for (int i = 0; i < m; i++)
    {
        fin >> a >> b;
        g.insert_edge(a, b);
    }
    vector<vector<int> > aux;
    aux = g.biconnected_comp();
    fout << aux.size() << '\n';
    for (int i = 0; i < aux.size(); i++)
    {
        for (int j = 0; j < aux[i].size(); j++)
            fout << aux[i][j] + 1 << " ";
        fout << '\n';
    }
}