Cod sursa(job #2513887)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 23 decembrie 2019 23:25:02
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <stack>
#define N 100005
#define ll long long
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<ll>a[N], sol[2*N];
stack<ll> st;
ll v[N], h[N], k=0;
void dfs(ll i, ll j){
    ll doamnedasamacalceomasinaodatanumaisuportjeguastadeproblemafmmdecacat;
    v[i]=h[i]=j;
    st.push(i);
    for(auto it:a[i]){
        if(!v[it]){
            doamnedasamacalceomasinaodatanumaisuportjeguastadeproblemafmmdecacat=st.size();
            dfs(it, j+1);
            v[i]=min(v[i], v[it]);
            if(v[it]>=j){
                sol[++k].push_back(i);
                while(!st.empty() && st.size()!=doamnedasamacalceomasinaodatanumaisuportjeguastadeproblemafmmdecacat){
                    sol[k].push_back(st.top());
                    st.pop();
                }
            }
        }
        v[i]=min(v[i], h[it]);
    }
}
int main() { 
    ll n,m,i,x,y;
    in>>n>>m;
    for(i=0; i<m; ++i){
        in>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,1);
    out<<k<<"\n";
    for(i=1; i<=k; ++i){
        for(auto it:sol[i])
            out<<it<<" ";
        out<<"\n";
    }
    return 0;
}