Cod sursa(job #2884011)

Utilizator servus2022Stefan Tonut servus2022 Data 2 aprilie 2022 10:50:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

typedef vector < int > VI;

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

int N;
vector < int > G[NMAX];

int Level[NMAX], Low[NMAX];

stack < int > St;

vector < VI > Sol;

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;

    int M = 0;
    f >> M;

    for(int e = 1; e <= M; ++e)
    {
        int u = 0, v = 0;
        f >> u >> v;

        Add_Edge(u, v);
    }

    return;
}

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

static inline void DFS (int Node = ROOT, int from = 0, int level = 1)
{
    Level[Node] = Low[Node] = level;

    St.push(Node);

    for(auto it : G[Node])
        if(!Level[it])
        {
            DFS(it, Node, level + 1);

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

            if(Low[it] >= Level[Node])
            {
                VI comp;
                int Top = 0;

                do
                {
                    Top = St.top(), comp.push_back(Top);
                    St.pop();
                }
                while(Top != it);

                comp.push_back(Node);

                Sol.push_back(comp);
            }
        }
        else
            Low[Node] = my_min(Low[Node], Level[it]);

    return;
}

static inline void Write ()
{
    g << (int)Sol.size() << '\n';

    for(auto it : Sol)
    {
        sort(it.begin(), it.end());

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

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

        g << '\n';
    }

    return;
}

static inline void Solve ()
{
    DFS();

    Write();

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}