Cod sursa(job #3222329)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 9 aprilie 2024 18:48:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
using i64=int64_t;
const int inf=1e9;
const int N=1e5;
int low[N],tin[N];
struct Edge
{
    int x,y;
};
stack<Edge>sk;
vector<vector<int>>comps;
vector<int>g[N];
int n,m;

void pop_comp(int x,int y)
{
    vector<int>acum;
    while(sk.top().x!=x || sk.top().y!=y)
    {
        acum.pb(sk.top().x);
        acum.pb(sk.top().y);
        sk.pop();
    }
    acum.pb(sk.top().x);
    acum.pb(sk.top().y);
    sk.pop();
    comps.pb(acum);
}
void dfs(int nod,int tt)
{
    static int now=0;
    low[nod]=tin[nod]=++now;
    for(auto &c:g[nod])
    {
        if(c==tt)
        {
            continue;
        }
        if(!low[c])
        {
            sk.push({nod,c});
            dfs(c,nod);
            low[nod]=min(low[nod],low[c]);
            if(low[c]>=tin[nod])
            {
                pop_comp(nod,c);
            }
        }
        else
        {
            low[nod]=min(low[nod],tin[c]);
        }
    }
}
main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(0,0);
    cout<<comps.size()<<'\n';
    for(auto &v:comps)
    {
        sort(all(v));
        v.erase(unique(all(v)) , v.end());
        for(auto &c:v)
        {
            cout<<c+1<<' ';
        }
        cout<<'\n';
    }
}