Cod sursa(job #3364380)

Utilizator CarenaMironov Cezar Luca Carena Data 2 septembrie 2026 13:19:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>
#define fr first
#define sc second

using namespace std;

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

const int NMAX=1e5+5;
int n, m, d[NMAX], low[NMAX];
vector<int> adj[NMAX];
vector<vector<int>> bcc;
stack<pair<int, int>> st;

void DFS(int u, int pu)
{
    d[u]=d[pu]+1;
    low[u]=d[u];
    for(auto v:adj[u])
    {
        if(v==pu || d[v]>d[u])
            continue;
        if(d[v]==0)
        {
            st.push({u, v});
            DFS(v, u);
            low[u]=min(low[u], low[v]);
            if(low[v]>=d[u])
            {
                bcc.push_back({u, v});
                while(st.top()!=make_pair(u, v))
                {
                    bcc.back().push_back(st.top().sc);
                    st.pop();
                }
                st.pop();
            }
        }
        else
            low[u]=min(low[u], d[v]);
    }
}

int main()
{
    in>>n>>m;
    while(m--)
    {
        int a, b; in>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    DFS(1, 0);
    out<<bcc.size()<<'\n';
    for(auto b:bcc)
    {
        for(auto u:b)
            out<<u<<" ";
        out<<'\n';
    }
    return 0;
}