Cod sursa(job #2723193)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 13 martie 2021 19:07:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 1e5 + 1;
const int ROOT = 1;

int N, M;

int Level[NMAX], Low[NMAX];

vector < int > G[NMAX];

stack < int > Stack;

vector < vector < int > > Sol;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int X = 0, Y = 0;
        f >> X >> Y;

        G[X].push_back(Y), G[Y].push_back(X);
    }

    return;
}

static inline int my_min (int a, int b)
{
    return ((a < b) ? a : b);
}

static inline void DFS (int Node, int L = 1)
{
    Level[Node] = Low[Node] = L;

    Stack.push(Node);

    for(auto it : G[Node])
        if(Level[it])
            Low[Node] = my_min(Low[Node], Level[it]);
        else
        {
            DFS(it, L + 1);

            Low[Node] = my_min(Low[Node], Low[it]);

            if(Low[it] >= Level[Node])
            {
                vector < int > sol;

                int Elem = 0;

                do
                {
                    Elem = Stack.top(), sol.push_back(Elem);

                    Stack.pop();
                }
                while(Elem != it);

                sol.push_back(Node);

                Sol.push_back(sol);
            }
        }

    return;
}

static inline void Solve ()
{
    DFS(ROOT);

    g << (int)Sol.size() << '\n';

    for(auto it : Sol)
    {
        for(int j = 0; j < (int)it.size(); ++j)
        {
            g << it[j];

            if(j != (int)it.size() - 1)
                g << ' ';
        }

        g << '\n';
    }

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}