Cod sursa(job #2376319)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 martie 2019 14:51:22
Problema Componente biconexe Scor 90
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;
std::vector <int> ADC[MAXN];
std::vector <std::vector <int>> Biconex;
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]) {
                Biconex.push_back(std::vector <int> ());

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

                Biconex.back().push_back(Edge);
                Biconex.back().push_back(Vertex);
                Edges.pop();

                std::sort(Biconex.back().begin(), Biconex.back().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 << Biconex.size() << '\n';
    for (auto Component:Biconex) {
        for (auto Vertex:Component)
            Out << Vertex << ' ';
        Out << '\n';
    }
}

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

    return 0;
}