Cod sursa(job #3293695)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 12 aprilie 2025 12:37:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

const int N = 1e5;
int low[N + 1], discover[N + 1];

vector <int> g[N + 1], sol[N + 1];

int n, m, x, y, c, timp;

stack <int> s;

void dfs (int node, int tata)
{
    discover[node] = low[node] = ++timp;
    s.push(node);
    for (auto it : g[node])
    {
        if (!discover[it])
        {
            dfs (it, node);
            low[node] = min (low[node], low[it]);
            if (low[it] > discover[node]);///node-it (bridge)
            if (low[it] >= discover[node])
            {
                ///node punct de articulatie
                sol[++c].push_back(node);
                while (!s.empty() && s.top() != it)
                    sol[c].push_back(s.top()), s.pop();
                if (!s.empty())
                    sol[c].push_back(s.top()), s.pop();
            }
        }
        else
        {
            if (it != tata)
                low[node] = min (low[node], discover[it]);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs (1, 0);
    cout << c << '\n';
    for (int i = 1; i <= c; ++i, cout << '\n')
        for (auto it : sol[i])
            cout << it << ' ';
    return 0;
}