Cod sursa(job #3374649)

Utilizator valexandreiValeanu Alexandru-Andrei valexandrei Data 9 noiembrie 2026 08:25:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, timp, topNod, topApel;
int niv[100005], low[100005], tata[100005], poz[100005], stNod[100005], stApel[100005];
vector<int> g[100005];
vector<vector<int>> sol;

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int s = 1; s <= n; s++)
    {
        if (niv[s])
            continue;
        niv[s] = low[s] = ++timp;
        stNod[topNod++] = s;
        stApel[topApel++] = s;
        while (topApel)
        {
            int u = stApel[topApel - 1];
            if (poz[u] < (int)g[u].size())
            {
                int v = g[u][poz[u]++];
                if (v == tata[u])
                    continue;
                if (niv[v])
                    low[u] = min(low[u], niv[v]);
                else
                {
                    tata[v] = u;
                    niv[v] = low[v] = ++timp;
                    stNod[topNod++] = v;
                    stApel[topApel++] = v;
                }
            }
            else
            {
                topApel--;
                int p = tata[u];
                if (p)
                {
                    low[p] = min(low[p], low[u]);
                    if (low[u] >= niv[p])
                    {
                        vector<int> c;
                        while (true)
                        {
                            int w = stNod[--topNod];
                            c.push_back(w);
                            if (w == u)
                                break;
                        }
                        c.push_back(p);
                        sol.push_back(c);
                    }
                }
            }
        }
        topNod--;
    }
    fout << sol.size() << "\n";
    for (auto &c : sol)
    {
        for (int x : c)
            fout << x << " ";
        fout << "\n";
    }
    return 0;
}