Cod sursa(job #2972903)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 30 ianuarie 2023 16:44:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");

int n,m,a,b;
vector<vector<int>> sirad;
stack<pair<int,int>>stk;
vector<int> lvl,low;
vector<vector<int>>cbc;

void cache(int a,int b)
{
    vector<int> c;
    while(true)
    {
        int tx = stk.top().first,
        ty = stk.top().second;
        c.push_back(tx);
        c.push_back(ty);
        stk.pop();
        if(tx == a  && ty == b)break;
    }
    cbc.push_back(c);
}
void Bicon(int x,int parent,int idx)
{
    lvl[x] = low[x] = idx;

    for(auto i : sirad[x])
    {
        if(i==parent)continue;
        if(lvl[i] == -1)
        {
            stk.push({x,i});
            Bicon(i,x,idx+1);
            low[x] = min(low[x],low[i]);
            if(low[i] >= lvl[x])
                cache(x,i);
        }
        else low[x] = min(low[x],lvl[i]);
    }
}
void compute()
{
    for(int i=1;i<=n;++i)
        if(lvl[i] == -1)
            Bicon(i,0,0);
}
int main()
{
    cin>>n>>m;
    sirad = vector<vector<int>>(n+1);
    lvl = low = vector<int>(n+1,-1);
    while(m--)
    {
        cin>>a>>b;
        sirad[a].push_back(b);
        sirad[b].push_back(a);
    }

    compute();

    cout<<cbc.size()<<'\n';
    for(auto& i : cbc)
    {
        sort(i.begin(),i.end());
        i.erase(unique(i.begin(),i.end()),i.end());
        for(auto j : i)
            cout<<j<<' ';
        cout<<'\n';
    }
    return 0;
}