Cod sursa(job #3192819)

Utilizator poparobertpoparobert poparobert Data 13 ianuarie 2024 11:54:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 11.8 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <cmath>
#include <string>
#include <deque>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <windows.h>
#include <complex>
#pragma GCC optimize("fast-math")
using namespace std;
using namespace __gnu_pbds;
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define lsb(x) ((x) & (-x))
#define msb(x) ((x) == 0 ? 0 : (1 << (64 - __builtin_clzll(x) - 1)))
#define DX return cout<<ans[0],void();
#define XD return cout<<ans[1],void();
#define bleacs(x) return cout<<x<<'\n',void();
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
mt19937_64 rng(chrono :: steady_clock :: now().time_since_epoch().count());

const size_t fixed_random = rng();

clock_t start_time = clock(), end_time;

ll random_seed(ll modulo) {
    return rng() % modulo;
}

template <typename T>
inline void hash_combine(size_t& seed, const T& value) {
    seed ^= hash<T>{}(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct pair_hash {
    template <typename T1, typename T2>
    size_t operator () (const pair<T1, T2>& p) const {
        size_t seed = fixed_random;

        hash_combine(seed, p.first);
        hash_combine(seed, p.second);

        return seed;
    }
};

struct normal_hash {
    template <typename T>
    size_t operator () (const T& p) const {
        size_t seed = fixed_random;

        hash_combine(seed, p);

        return seed;
    };
};
template<typename T,typename V>istream& operator>>(istream&in,pair<T,V>&a){in>>a.first>>a.second;return in;}
template<typename T,typename V>ostream& operator<<(ostream&out,const pair<T,V>&a){out<<a.first<<' '<<a.second;return out;}
template<typename T>istream& operator>>(istream&in,vector<T> &a){for(typename vector<T>::iterator i=a.begin();i!=a.end();i++)cin>>*i;return in;}
template<typename T>ostream& operator<<(ostream&out,const vector<T>&a){for(T x:a)out<<x<<' ';return out;}
template<typename T,typename V,typename X,typename Z> pair<T,V>operator+(const pair<T,V> &a,const pair<X,Z>&b){return {a.first+b.first,a.second+b.second};}
template<typename T,typename V,typename X,typename Z> pair<T,V>operator-(const pair<T,V> &a,const pair<X,Z>&b){return {a.first-b.first,a.second-b.second};}
template<typename T,typename V> vector<T> operator+(const vector<T>&a,const vector<V> &b){vector<T> rez;if(a.size()!=b.size())return rez;for(ll i=0;i<a.size();i++)rez.pb(a[i]+b[i]);return rez;}
template<typename T,typename V> T operator+=(T &a,const V &b){return a=a+b;}
ll gcd(ll a,ll b){ll r;while(b)r=a%b,a=b,b=r;return a;}
ll mod=1e9+7;
ll inf=3*1e18;
class AIB{
    vector<ll> v;
public:
    AIB(ll n){v.resize(n+1);}
    void add(ll p,ll val=1){for(;p<v.size();p+=lsb(p))v[p]+=val;}
    ll ask(ll p){ll rez=0;for(;p;p-=lsb(p))rez+=v[p];return rez;}
};
ll fastexp(ll b,ll e,ll mod=mod)
{
    ll rez=1;
    while(e)
    {
        if(e&1)rez=rez*b%mod;
        b=b*b%mod;
        e>>=1;
    }
    return rez;
}
string pi="3141592653589793238462643383279502884197169399375105820974944";
/*class minaint{
    vector<ll>v;
    ll n;
public:
    minaint(ll x=0){n=x;v.resize(2*n+5);}
    build(vector<ll>&a)
    {
        ll i;
        for(i=1;i<=n;i++)v[i+n]=a[i];
        for(i=n;i>=1;i--)v[i]=min(v[i<<1],v[i<<1|1]);
    }
    ll ask(ll l,ll r)
    {
        ll rez=1e15;
        for(l+=n,r+=n+1;l<r;l>>=1,r>>=1)
        {
            if(l&1)rez=min(rez,v[l++]);
            if(r&1)rez=min(rez,v[--r]);
        }
        return rez;
    }
};*/
/*class maxaint{
    vector<ll>v;
    ll n;
public:
    maxaint(ll x=0){n=x;v.resize(2*n+5);}
    build(vector<ll>&a)
    {
        build()
    }
};*/
/*class AINTfirstlast{
    vector<ll> v,v2;
    ll n;
    void build(vector<ll>&a,ll l,ll r,ll p)
    {
        if(l==r)return v2[p]=v[p]=a[l],void();
        ll mid=(l+r)/2;
        build(a,l,mid,p+1);
        build(a,mid+1,r,p+2*(mid-l+1));
        v[p]=min(v[p+1],v[p+2*(mid-l+1)]);
        v2[p]=max(v2[p+1],v2[p+2*(mid-l+1)]);
    }
    pll firstsmaller(ll l,ll r,ll val,ll il,ll ir,ll p)
    {
        //cerr<<il<<' '<<ir<<' '<<p<<' '<<v[p]<<endl;
        ll mid=(il+ir)/2;
        if(il==ir)return {v[p],il};
        if(l<=il&&ir<=r)
        {
            if(v[p+1]<=val) return {v[p],firstsmaller(l,r,val,il,mid,p+1).second};
            return {v[p],firstsmaller(l,r,val,mid+1,ir,p+2*(mid-il+1)).second};
        }
        if(l>mid)return firstsmaller(l,r,val,mid+1,ir,p+2*(mid-il+1));
        if(r<=mid)return firstsmaller(l,r,val,il,mid,p+1);
        pll st,dr;
        dr=firstsmaller(l,r,val,mid+1,ir,p+2*(mid-il+1));
        st=firstsmaller(l,r,val,il,mid,p+1);
        if(st.first<=val)return st;
        return dr;
    }
    pll lastsmaller(ll l,ll r,ll val,ll il,ll ir,ll p)
    {
        //cerr<<il<<' '<<ir<<' '<<p<<' '<<v[p]<<endl;
        ll mid=(il+ir)/2;
        if(il==ir)return {v[p],il};
        if(l<=il&&ir<=r)
        {
            if(v[p+2*(mid-il+1)]<=val) return {v[p],lastsmaller(l,r,val,mid+1,ir,p+2*(mid-il+1)).second};
            return {v[p],lastsmaller(l,r,val,il,mid,p+1).second};
        }
        if(l>mid)return lastsmaller(l,r,val,mid+1,ir,p+2*(mid-il+1));
        if(r<=mid)return lastsmaller(l,r,val,il,mid,p+1);
        pll st,dr;
        dr=lastsmaller(l,r,val,mid+1,ir,p+2*(mid-il+1));
        st=lastsmaller(l,r,val,il,mid,p+1);
        if(dr.first<=val)return dr;
        return st;
    }
    pll firstbigger(ll l,ll r,ll val,ll il,ll ir,ll p)
    {
        //cerr<<il<<' '<<ir<<' '<<p<<' '<<v[p]<<endl;
        ll mid=(il+ir)/2;
        if(il==ir)return {v2[p],il};
        if(l<=il&&ir<=r)
        {
            if(v2[p+1]>=val) return {v2[p],firstbigger(l,r,val,il,mid,p+1).second};
            return {v2[p],firstbigger(l,r,val,mid+1,ir,p+2*(mid-il+1)).second};
        }
        if(l>mid)return firstbigger(l,r,val,mid+1,ir,p+2*(mid-il+1));
        if(r<=mid)return firstbigger(l,r,val,il,mid,p+1);
        pll st,dr;
        dr=firstbigger(l,r,val,mid+1,ir,p+2*(mid-il+1));
        st=firstbigger(l,r,val,il,mid,p+1);
        if(st.first>=val)return st;
        return dr;
    }
    pll lastbigger(ll l,ll r,ll val,ll il,ll ir,ll p)
    {
        //cerr<<il<<' '<<ir<<' '<<p<<' '<<v[p]<<endl;
        ll mid=(il+ir)/2;
        if(il==ir)return {v2[p],il};
        if(l<=il&&ir<=r)
        {
            if(v2[p+2*(mid-il+1)]>=val) return {v2[p],lastbigger(l,r,val,mid+1,ir,p+2*(mid-il+1)).second};
            return {v2[p],lastbigger(l,r,val,il,mid,p+1).second};
        }
        if(l>mid)return lastbigger(l,r,val,mid+1,ir,p+2*(mid-il+1));
        if(r<=mid)return lastbigger(l,r,val,il,mid,p+1);
        pll st,dr;
        dr=lastbigger(l,r,val,mid+1,ir,p+2*(mid-il+1));
        st=lastbigger(l,r,val,il,mid,p+1);
        if(dr.first>=val)return dr;
        return st;
    }
public:
    AINT(ll x=0){n=x,v.resize(2*x+3),v2.resize(2*x+3);}
    void build(vector<ll> &a)
    {
        build(a,1,n,1);
    }
    ll firstsmaller(ll l,ll r,ll val)
    {
        return firstsmaller(l,r,val,1,n,1).second;
        //daca nu exista se returneaza r
    }
    ll lastsmaller(ll l,ll r,ll val)
    {
        return lastsmaller(l,r,val,1,n,1).second;
        //daca nu exista se returneaza l
    }
    ll firstbigger(ll l,ll r,ll val)
    {
        return firstbigger(l,r,val,1,n,1).second;
        //daca nu exista se returneaza r
    }
    ll lastbigger(ll l,ll r,ll val)
    {
        return lastbigger(l,r,val,1,n,1).second;
        //daca nu exista se returneaza l
    }
};*/
class AINT
{
    ll n;
    vector<ll> v,lazy;
    void push(ll p)
    {
        v[p]+=lazy[p];
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        lazy[p]=0;
    }
    ll getval(ll p)
    {
        return v[p]+lazy[p];
    }
    void add(ll st,ll dr,ll p,ll l,ll r,ll val)
    {
        if(l<=st&&dr<=r)
        {
            lazy[p]+=val;
            return;
        }
        ll mid=(st+dr)/2;
        push(p);
        if(l<=mid)
            add(st,mid,p<<1,l,r,val);
        if(r>mid)
        add(mid+1,dr,p<<1|1,l,r,val);
        v[p]=max(getval(p<<1),getval(p<<1|1));
    }
    ll ask(ll st,ll dr,ll p,ll l,ll r)
    {
        if(l<=st&&dr<=r)
        {
            return getval(p);
        }
        ll mid=(st+dr)/2;
        push(p);
        ll a=0,b=0;
        if(l<=mid)
            a=ask(st,mid,p<<1,l,r);
        if(r>mid)
        b=ask(mid+1,dr,p<<1|1,l,r);
        return max(a,b);
    }
public:
    AINT(ll x=0){n=x,v.resize(4*x+5),lazy.resize(4*x+5);}
    void add(ll l,ll r,ll val)
    {
        add(1,n,1,l,r,val);
    }
    ll ask(ll l,ll r)
    {
        if(l>r)return 0ll;
        return ask(1,n,1,l,r);
    }
};
void addmod(ll &x,ll y,ll modu=mod)
{
    x+=y;
    if(x>=mod)x-=modu;
    if(x<0)x+=modu;
}
void multmod(ll &x,ll y,ll modu=mod)
{
    x=x*y%modu;
}
string ans[]={"No\n","Yes\n"};
ll maxitaxi;
vector<vector<ll>>divs;
vector<ll>fact,inv;
void eratostene(bool doarprime=0)
{
    ll i,j;
    divs.resize(maxitaxi+1);
    for(i=1;i<=maxitaxi;i++)
    {
        if(doarprime&&divs[i].size()>1)
            continue;
        for(j=i;j<=maxitaxi;j+=i)
            divs[j].pb(i);
    }
}
void precalcfact()
{
    ll i,j;
    fact.resize(maxitaxi+1);
    inv.resize(maxitaxi+1);
    fact[0]=inv[0]=1;
    for(i=1;i<=maxitaxi;i++)
    {
        fact[i]=fact[i-1]*i%mod;
        inv[i]=fastexp(fact[i],mod-2,mod);
    }
}
ll comb(ll n,ll k)
{
    if(k<0||k>n)
        return 0ll;
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
ll catalan(ll n)
{
    return comb(2*n,n)*fastexp(n+1,mod-2)%mod;
}
void constsetup()
{
    maxitaxi=1e5;
    mod=998244353;
    eratostene();
    precalcfact();
}
void setup()
{

}
struct comp{
    bool operator()(pll a,pll b)
    {
        return !(a.first!=b.first?a.first<b.first:a.second>b.second);
    }
};
void solve(ll T)
{
    ll n,m,i,j,k,l,x,y;
    cin>>n>>m;
    vector<vector<ll>>vec(n+1);
    vector<ll>depth(n+1),timp(n+1);
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        vec[x].pb(y);
        vec[y].pb(x);
    }
    vector<vector<ll>>rez;
    vector<ll>emp;
    stack<ll> aux;
    function<void(ll)>tarjan=[&](ll x)
    {
        ll mn=1e15;
        aux.push(x);
        for(ll y:vec[x])
        {
            if(depth[y]==0)
            {
                depth[y]=depth[x]+1;
                tarjan(y);
                mn=min(mn,timp[y]);
                if(timp[y]<depth[x])continue;
                rez.pb(emp);
                while(aux.top()!=y)
                {
                    rez.back().pb(aux.top());
                    aux.pop();
                }
                rez.back().pb(y);
                aux.pop();
                rez.back().pb(x);
            }
            else
                mn=min(mn,depth[y]);
        }
        timp[x]=min(depth[x],mn);
    };
    depth[1]=1;
    tarjan(1);
    cout<<rez.size()<<'\n';
    for(i=0;i<rez.size();i++)
    {
        cout<<rez[i]<<'\n';
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll c=0;
    constsetup();
    setup();
    //ll t;cin>>t;while(t--)
		solve(++c);
    return 0;
}