Cod sursa(job #3152312)

Utilizator andiRTanasescu Andrei-Rares andiR Data 24 septembrie 2023 16:53:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

int n, m, nrc;
vector <int> ad[Nmax];
int lvl[Nmax];
bool vis[Nmax];
stack <int> st;
vector <int> sol[Nmax];
int dfs(int nod, int p){
    if (vis[nod])
        return lvl[nod];
    vis[nod]=1;
    lvl[nod]=lvl[p]+1;
    st.push(nod);
    int mn=lvl[nod];
    for (auto it:ad[nod]){
        int crt;
        if (it!=p && !vis[it]){
            crt=dfs(it, nod);
            mn=min(mn, crt);
            if (crt>=lvl[nod]){
                while (st.top()!=it){
                    sol[nrc].pb(st.top());
                    st.pop();
                }
                sol[nrc].pb(st.top());
                sol[nrc].pb(nod);
                st.pop();
                nrc++;
            }
        }
        else if (it!=p){
            crt=dfs(it, nod);
            mn=min(mn, crt);
        }
    }
    return mn;
}
inline void hopcraft_tarjan(){
    lvl[n]=-1;
    for (int i=0; i<n; i++)
        if (!vis[i])
            dfs(i, n);
}
int main()
{
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/

    fin>>n>>m;
    int a, b;
    for (int i=0; i<m; i++){
        fin>>a>>b;
        a--; b--;
        ad[a].pb(b);
        ad[b].pb(a);
    }
    hopcraft_tarjan();
    fout<<nrc<<'\n';
    for (int i=0; i<nrc; i++){
        for (auto it:sol[i])
            fout<<it+1<<' ';
        fout<<'\n';
    }
    return 0;
}