Cod sursa(job #3214857)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 14 martie 2024 15:11:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

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

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

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

stack <int> s;

void dfs (int node, int parent)
{
    low[node] = discover[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 e punct de articulatie
                ++len;
                while (!s.empty() && s.top() != it)
                    l[len].push_back(s.top()), s.pop();
                if (!s.empty())
                    l[len].push_back(s.top()), s.pop();
                l[len].push_back(node);
            }
            if (low[it] > discover[node]);///e bridge
        }
        else
        {
            if (it != parent && discover[it] < discover[node])///daca am muchie back si e stramos
                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 << len << '\n';
    for (int i = 1; i <= len; ++i, cout << '\n')
        for (auto it : l[i])
        cout << it << ' ';
    return 0;
}