Cod sursa(job #3370067)

Utilizator Razvan23Razvan Mosanu Razvan23 Data 23 octombrie 2026 21:13:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<vector<int>> L;
vector<int> timpi;
vector<int> low;
vector<int> viz;
int contor;
vector<int> critice;
vector<int> st;
vector<vector<int>> componente;

void DFS(int f, int p = -1)
{
    viz[f] = 1;
    timpi[f] = low[f] = ++contor;
    int copii = 0;
    st.push_back(f);
    for(const auto& w: L[f])
    {
        if(w == p) continue;
        if(viz[w] == 0)
        {
            copii++;
            DFS(w, f);
            low[f] = min(low[w], low[f]);
            if(low[w] >= timpi[f]) 
            {
                if(p != -1) critice[f] = 1;
                vector<int> aux;
                int nod;
                do
                {
                    nod = st.back();
                    st.pop_back();
                    aux.push_back(nod);
                } while (nod != w);
                aux.push_back(f);
                componente.push_back(aux);
            }
        }
        else low[f] = min(low[f], timpi[w]);
    }
    if(p == -1 && copii > 1) critice[f] = 1;
}

int main()
{
    int i, x, y;
    fin >> n >> m;
    L.resize(n + 1);
    viz.resize(n + 1, 0);
    low.resize(n + 1, 2e9);
    timpi.resize(n + 1, 0);
    critice.resize(n + 1, 0);
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    for(i = 1; i <= n; i++)
        if(viz[i] == 0) DFS(i);
    //for(i = 1; i <= n; i++)
    //    fout << critice[i] << " ";
    fout << componente.size() << "\n";
    for(const auto& w: componente)
    {
        for(const auto& v: w)
            fout << v << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}