Cod sursa(job #2376325)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 martie 2019 14:53:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>

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

#define MAXN 100005

int N, M, BiconexSize;
std::vector <int> ADC[MAXN];
std::vector <int> Biconex[MAXN];

inline void AddEdge(int X, int Y) {
    ADC[X].push_back(Y);
    ADC[Y].push_back(X);
}

int Discovery[MAXN], Lowlink[MAXN];
int Time;
std::stack <int_pair> Edges;
void DFS(int Vertex = 1) {
    Discovery[Vertex] = Lowlink[Vertex] = ++Time;
    for (auto Edge:ADC[Vertex]) {
        if (Discovery[Edge])
            Lowlink[Vertex] = std::min(Lowlink[Vertex], Discovery[Edge]);
        else {
            Edges.push({Vertex, Edge});
            DFS(Edge);

            Lowlink[Vertex] = std::min(Lowlink[Vertex], Lowlink[Edge]);
            if (Discovery[Vertex] <= Lowlink[Edge]) {
                ++ BiconexSize;

                while (Edges.top().first != Vertex)
                    Biconex[BiconexSize].push_back(Edges.top().second),
                    Edges.pop();

                Biconex[BiconexSize].push_back(Edge);
                Biconex[BiconexSize].push_back(Vertex);
                Edges.pop();

                std::sort(Biconex[BiconexSize].begin(), Biconex[BiconexSize].end());
            }
        }
    }
}

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

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y; i<=M; ++i)
        In >> X >> Y, AddEdge(X, Y);
}

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

    Out << BiconexSize << '\n';
    for (int i=1; i<=BiconexSize; ++i, Out << '\n')
        for (auto Vertex:Biconex[i])
            Out << Vertex << ' ';
}

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

    return 0;
}