Cod sursa(job #2321859)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 16 ianuarie 2019 18:37:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

#define MAXN 100005
#define int_pair std::pair <int, int>

int N, M, NBicnx;
std::vector <int> ADC[MAXN], Bicnx[MAXN];

inline void AddEdge(int x, int y) {
    ADC[x].push_back(y);
    ADC[y].push_back(x);
}

std::ifstream In("biconex.in");
std::ofstream Out("biconex.out");

std::stack <int_pair> Stack;
int LVL[MAXN], Low[MAXN], Steps;

void DFS(int Vertex) {
    LVL[Vertex] = Low[Vertex] = ++Steps;

    for (auto Vecin:ADC[Vertex]) {
        if (!LVL[Vecin]) {
            Stack.push({Vertex, Vecin});
            DFS(Vecin);

            Low[Vertex] = std::min(Low[Vertex], Low[Vecin]);

            if (Low[Vecin] >= LVL[Vertex]) {
                while (Stack.top().first != Vertex)
                    Bicnx[NBicnx].push_back(Stack.top().second),
                    Stack.pop();

                Bicnx[NBicnx].push_back(Stack.top().first);
                Bicnx[NBicnx].push_back(Stack.top().second);
                Stack.pop();

                std::sort(Bicnx[NBicnx].begin(), Bicnx[NBicnx].end());
                ++ NBicnx;
            }
        }
        else Low[Vertex] = std::min(Low[Vertex], LVL[Vecin]);
    }
}

void Citire() {
    In >> N >> M;
    for (int i=0, x, y; i<M; ++i)
        In >> x >> y, AddEdge(x, y);
}

void Rezolvare() {
    for (int i=1; i<=N; ++i)
        if (!LVL[i])
            DFS(i);

    Out << NBicnx << '\n';
    for (int i=0, j; i<NBicnx; ++i, Out << '\n')
        for (j=0; j<Bicnx[i].size(); ++j)
            Out << Bicnx[i][j] << ' ' ;
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}