Cod sursa(job #3203613)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 14 februarie 2024 04:06:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#pragma GCC optimize ("O3")

using namespace std;

ifstream cin  ("biconex.in");
ofstream cout ("biconex.out");

const int LIM = 300000;
int n, m;
vector<int> edge[LIM + 5];
int cbc;
vector<int> CBC[LIM + 5];

int lvl[LIM + 5], low[LIM + 5];
bitset<LIM + 5> viz;
stack<int> stk;
inline void tarjan(int crt, int prv, int level){
    viz[crt] = true;
    lvl[crt] = low[crt] = level;
    stk.push(crt);

    for(auto nxt : edge[crt])
        if(nxt != prv){
            if(!viz[nxt]){
                tarjan(nxt, crt, level+1);
                low[crt] = min(low[crt], low[nxt]);

                if(low[nxt] >= lvl[crt]){
                    cbc++;

                    while(!stk.empty() && stk.top() != nxt){
                        CBC[cbc].push_back(stk.top());
                        stk.pop();
                    }
                    stk.pop();
                    CBC[cbc].push_back(nxt);
                    CBC[cbc].push_back(crt);
                }
            }else{
                low[crt] = min(low[crt], lvl[nxt]);
            }
        }
}

int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin>>n>>m;
    for(int i=1, u, v; i<=m; i++){
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    for(int i=1; i<=n; i++)
        if(!viz[i])
            tarjan(i, 0, 1);

    cout<<cbc<<"\n";
    for(int i=1; i<=cbc; i++){
        for(auto nod : CBC[i])
            cout<<nod<<" ";
        cout<<"\n";
    }
    return 0;
}
/**
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 5
7 8
**/