Cod sursa(job #3292180)

Utilizator robert_dumitruDumitru Robert Ionut robert_dumitru Data 7 aprilie 2025 11:40:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, nrC;
int nma[100005], nivel[100005];
bitset<100005> viz;
vector<int> L[100005], comp[100005];
stack<int> st;

void DFS(int k, int tata)
{
    viz[k] = 1;
    st.push(k);
    nivel[k] = nma[k] = nivel[tata] + 1;
    for (int i : L[k])
        if (i != tata)
        {
            if (viz[i] == 1)
                nma[k] = min(nma[k], nivel[i]);
            else
            {
                DFS(i, k);
                nma[k] = min(nma[k], nma[i]);
                if (nivel[k] <= nma[i])
                {
                    nrC++;
                    while (st.top() != i)
                    {
                        comp[nrC].push_back(st.top());
                        st.pop();
                    }
                    st.pop();
                    comp[nrC].push_back(i);
                    comp[nrC].push_back(k);
                }
            }
        }
}

int main()
{
    int i, j;
    fin >> n >> m;
    while (m--)
    {
        fin >> i >> j;
        L[i].push_back(j);
        L[j].push_back(i);
    }
    for (i = 1; i <= n; i++)
        if (viz[i] == 0) DFS(i, 0);

    fout << nrC << "\n";
    for (i = 1; i <= nrC; i++)
    {
        for (int j : comp[i])
            fout << j << " ";
        fout << "\n";
    }
    return 0;
}