Cod sursa(job #3344085)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 1 martie 2026 13:01:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

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

const int lim=1e5+10;
int n,m,low[lim],order[lim],timer,i,j,comp;
bool viz[lim];
stack<int> st;
vector <int> v[lim];
set <int> s[lim];
void dfs(int k,int origin)
{
    viz[k]=1;
    low[k]=order[k]=++timer;
    st.push(k);
    for(auto x:v[k])
    {
        if(x==origin)continue;
        if(viz[x]==1)low[k]=min(low[k],order[x]);
        else
        {
            dfs(x,k);
            low[k]=min(low[k],low[x]);
            if(order[k]<=low[x])
            {
                comp++;
                while(!st.empty()&&st.top()!=x)
                {
                    s[comp].insert(st.top());
                    st.pop();
                }
                st.pop();
                s[comp].insert(x);
                s[comp].insert(k);
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
    {
        dfs(i,0);
    }
    fout<<comp<<'\n';
    for(i=1;i<=comp;i++)
    {for(auto x:s[i])
    {
        fout<<x<<" ";
    }
    fout<<'\n';}
    return 0;
}