Cod sursa(job #2658066)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 13 octombrie 2020 09:36:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

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

int N, M;

vector < int > G[NMAX];

int Level[NMAX], Low[NMAX];

int K;
vector < int > List[NMAX];

stack < int > St;

static inline void Add_Edge (int X, int Y)
{
    G[X].push_back(Y), G[Y].push_back(X);

    return;
}

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;

        Add_Edge(X, Y);
    }

    return;
}

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

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

    St.push(Node);

    for(auto it : G[Node])
    {
        if(Level[it])
        {
            Low[Node] = my_min(Low[Node], Level[it]);

            continue;
        }

        DFS(it, Node);

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

        if(Low[it] >= Level[Node])
        {
            ++K, List[K].push_back(Node);

            int Top = 0;

            do
            {
                Top = St.top(), St.pop();

                List[K].push_back(Top);
            }
            while(Top != it);
        }
    }

    return;
}

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

    return;
}

static inline void Write ()
{
    g << K << '\n';

    for(int i = 1; i <= K; ++i)
    {
        for(int j = 0; j < (int)List[i].size(); ++j)
        {
            g << List[i][j];

            if(j != (int)List[i].size() - 1)
                g << ' ';
        }

        g << '\n';
    }

    return;
}

int main ()
{
    Read();

    Solve();

    Write();

    return 0;
}