Cod sursa(job #2535211)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 31 ianuarie 2020 17:23:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

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

constexpr int NMAX = 1e5 + 3;

int n, m;
vector <int> G[NMAX];

int Nivel[NMAX];
int Low[NMAX];

vector <vector <int> > sol;

deque <pair <int, int> > D;

void Drum (pair <int, int> muchie)
{
    vector <int> aux;

    while (!D.empty())
    {
        int x = D.back().first;
        int y = D.back().second;

        D.pop_back();

        aux.push_back(x);
        aux.push_back(y);

        if (x == muchie.first || y == muchie.second)
            break;
    }

    sort(aux.begin(), aux.end());
    sol.push_back(aux);
}

void Dfs (int node, int dad, int level)
{
    Low[node] = Nivel[node] = level;

    for (auto it : G[node])
    {
        if (it == dad) continue;

        if (Nivel[it] == -1)
        {
            D.push_back({node, it});

            Dfs(it, node, level+1);

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

            if (Low[it] >= Nivel[node])
                Drum({node, it});
        }
        else Low[node] = min(Low[node], Nivel[it]);
    }
}

int main()
{
    f >> n >> m;

    for (int i = 1; i <= n; ++i)
        Nivel[i] = -1;

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    Dfs(1, 0, 1);

    g << sol.size() << '\n';

    for (int i = 0; i < sol.size(); ++i)
    {
        g << sol[i][0] << " ";
        for (int j = 1; j < sol[i].size(); ++j)
            if (sol[i][j] != sol[i][j-1]) g << sol[i][j] << " ";
        g << '\n';
    }

    return 0;
}