Cod sursa(job #3285652)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 13 martie 2025 12:07:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

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

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

stack <int> s;

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

void dfs (int node, int tata)
{
    discover[node] = least[node] = ++timp;
    s.push(node);
    for (auto it : g[node])
    {
        if (!discover[it])
        {
            dfs (it, node);
            least[node] = min (least[node], least[it]);
            if (least[it] >= discover[node]) /// node e punct de articulatie
            {
                sol[++comp].push_back(node);
                while (!s.empty() && s.top() != it)
                    sol[comp].push_back(s.top()), s.pop();
                if (!s.empty())
                    sol[comp].push_back(s.top()), s.pop();
            }
        }
        else
        {
            if (it != tata)
                least[node] = min (least[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 << comp << '\n';
    for (int i = 1; i <= comp; ++i, cout << '\n')
        for (auto it : sol[i])
            cout << it << ' ';
    return 0;
}