Cod sursa(job #3222644)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 11 aprilie 2024 10:36:29
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int>v[100010],comp[100010];
int c[100010];
int n,m,lg,i,j,x,y,low[100010],viz[100010],niv[100010];
void bic(int node,int parent)
{
    viz[node]=1;
    low[node]=niv[node];
    c[++c[0]]=node;
    for(auto it:v[node])
        if(it!=parent)
        {
            if(viz[it])
            {
                low[node]=min(low[node],niv[it]);
                continue;
            }
            niv[it]=niv[node]+1;
            bic(it,node);
            low[node]=min(low[node],low[it]);
            if(low[it]>=niv[node])
            {
                lg++;
                int lst;
                do
                {
                    comp[lg].push_back(c[c[0]]);
                    lst=c[c[0]];
                    c[0]--;
                }while(c[0] && lst!=it);
                comp[lg].push_back(node);
            }
        }
}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bic(1,0);
    fout<<lg<<'\n';
    for(i=1;i<=lg;i++)
    {
        for(auto it:comp[i])
            fout<<it<<" ";
        fout<<'\n';
    }
    return 0;
}