Cod sursa(job #3030220)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 17 martie 2023 16:00:59
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
using pi = pair<int,int>;
int n,m,a,b;
vector<vector<int>> G;
vector<int> lvl,low;
stack<pi> stk;
vector<vector<int>> cbc;
vector<int> c;

void extract(int x,int y)
{
    c.clear();
    while(true)
    {
        int tx = stk.top().first,ty = stk.top().second;
        stk.pop();
        c.push_back(tx),c.push_back(ty);
        if(tx == x && ty == y)break;
    }
    sort(c.begin(),c.end());
    c.erase(unique(c.begin(),c.end()),c.end());
    cbc.push_back(c);
}
void Dfs(int x,int p)
{
    lvl[x] = low[x] = lvl[p] + 1;

    for(auto i : G[x])
        if(lvl[i] == 0)
        {
            stk.push({i,x});
            Dfs(i,x);
            low[x] = min(low[x],low[i]);
            if(low[i] >= lvl[x])
                extract(i,x);
        }
        else
            low[x] = min(low[x],lvl[i]);
}
int main()
{
    cin>>n>>m;
    G = vector<vector<int>>(n+1);
    lvl = low = vector<int>(n+1);
    while(m--)
    {
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    Dfs(1,0);

    cout<<cbc.size()<<'\n';
    for(auto i : cbc)
    {
        for(auto j : i)
            cout<<j<<' ';
        cout<<'\n';
    }
    return 0;
}