Cod sursa(job #3343950)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 28 februarie 2026 19:39:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int lim=1e5+10;
int n,m,i,timer,low[lim],order[lim],st[lim],sz,comp;
bool viz[lim];
vector <int> v[lim];
set <int> t[lim];

void dfs(int k,int origin)
{
    viz[k]=1;
    low[k]=order[k]=++timer;
    st[++sz]=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(sz>0&&st[sz]!=x)
                {
                    t[comp].insert(st[sz]);
                    sz--;
                }
                sz--;
                t[comp].insert(k);
                t[comp].insert(x);
            }
        }
    }
}
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:t[i])
            fout<<x<<" ";
        fout<<'\n';
    }
    return 0;
}