Cod sursa(job #3344642)

Utilizator amunnumeVlad Patrascu amunnume Data 4 martie 2026 13:47:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 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;
};
struct nod
{
    int depth,low;
    vector<int> edge;
    nod(): depth(0),low(0) {}
};
int n,m,i,j,x,y,sz,tot;
set<int> comp[M];
elem s[M];
nod v[M];
void read()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        v[x].edge.push_back(y);
        v[y].edge.push_back(x);
    }
}
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=++time;
    for(auto y:v[x].edge)
    {
        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)
            {
                cout<<x<<' '<<y<<endl;
                ///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()
{
    read();
    dfs(1,0);
    print();
    return 0;
}