Cod sursa(job #2533764)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 29 ianuarie 2020 17:58:01
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef pair < int, int > PII;

const int NMAX = 1e5 + 5;

int N, M, u, v;

vector < int > G[NMAX];

bool Sel[NMAX];

int Level[NMAX], Low[NMAX];

stack < PII > Stiva;

vector < vector < int > > Sol;

static inline void Add_Edge (int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);

    return;
}

static inline void F (int u, int v)
{
    vector < int > Aux;

    while(1)
    {
        int x = Stiva.top().first;
        int y = Stiva.top().second;

        Aux.push_back(x);
        Aux.push_back(y);

        Stiva.pop();

        if(x == u || y == v)
            break;
    }

    sort(Aux.begin(), Aux.end());

    Sol.push_back(Aux);

    return;
}

static inline void Go (int Node, int From, int Lvl)
{
    Level[Node] = Low[Node] = Lvl;

    for(auto it : G[Node])
    {
        if(it == From)
            continue;

        if(Level[it] == -1) /// Muchie de avans:
        {
            Stiva.push({Node, it});

            Go(it, Node, Lvl + 1);

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

            if(Low[it] >= Level[Node]) /// Nu poate ajunge mai sus de Node;
                F(Node, it);
        }
        else Low[Node] = min(Low[Node], Low[it]);
    }

    return;
}

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

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> u >> v;

        Add_Edge(u, v);
    }

    return;
}

int main()
{
    Read();

    memset(Level, -1, sizeof(Level));

    Go(1, 0, 1);

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

    for(auto it : Sol)
    {
        g << it[0] << ' ';

        for(int i = 1; i < (int)it.size(); ++i)
            if(it[i] != it[i - 1])
                g << it[i] << ' ';

        g << '\n';
    }

    return 0;
}