Cod sursa(job #3376659)

Utilizator amunnumeVlad Patrascu amunnume Data 18 noiembrie 2026 20:09:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int N=1e5+5,M=2e5+5;
struct elem
{
    int x,y;
}s[M];
struct node
{
    int depth,low,on_stack;
    vector<int> adj;
    node(): depth(0),low(0),on_stack(0) {}
}v[N];
int n,m,i,j,x,y,sz,tot;
set<int> comp[M];
void add_bcc(int x,int y)
{
    tot++;
    do
    {
        --sz;
        if(sz<0) break;
        comp[tot].insert(s[sz].x);
        comp[tot].insert(s[sz].y);
    }while(s[sz].x!=x || s[sz].y!=y);
}
void dfs(int x,int par)
{
    static int time=0;
    v[x].depth=v[x].low=v[par].depth+1;
    for(auto y:v[x].adj)
    {
        if(!v[y].depth)
        {
            s[sz++]={x,y};
            dfs(y,x);
            v[x].low=min(v[x].low,v[y].low);
            if(v[y].low>v[x].depth)
            {
                ///bridge
            }
            if(v[y].low>=v[x].depth)
            {
                add_bcc(x,y);
            }
        }
        else if(y!=par && v[y].depth<v[x].depth)
        {
            s[sz++]={x,y};
            v[x].low=min(v[x].low,v[y].depth);
        }
    }
}
void print()
{
    fout<<tot<<'\n';
    for(int i=1;i<=tot;++i)
    {
        for(auto it=comp[i].begin();it!=comp[i].end();++it)
            fout<<(*it)<<' ';
        fout<<'\n';
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        v[x].adj.push_back(y);
        v[y].adj.push_back(x);
    }
    for(i=1;i<=n;++i)
    {
        if(!v[i].depth) dfs(i,0);
    }
    print();
}