Cod sursa(job #3218328)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 26 martie 2024 20:54:40
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <bits/stdc++.h>
using namespace std;

///----------TOGGLES
#define FIO
#define LONGER
//#define TESTS
///---------

#ifdef LONGER
    #define int long long
#endif // LONGER

#ifdef FIO
    const string fname="biconex";
    ifstream in(fname+".in");
    ofstream out(fname+".out");
    #define cin in
    #define cout out
#endif // FIO

///--------

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

///-------STL++-----
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) x.size()
#define pb(x,y) x.push_back(y)
#define mp(x,y) make_pair(x,y)
#define fr(i,n) for(int i=1;i<=n;i++)
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pdd = pair<double, double>;
using veci = vector<int>;
using vecp = vector<pii>;
template<typename T> using PQ = priority_queue<T, vector<T>, greater<T> >;

///-----CODE GOES HERE-----

const int maxn = 1e5+5;
bool vis[maxn];
int h[maxn], ret[maxn];
veci g[maxn];
int n,m;

int ans=0;
int formula(int x)
{
    if(x<=2) return 0;
    return x*(x-1)*(x-2)/6;
}

vector<veci> comp;

veci stk;
void dfs(int nod)
{
    vis[nod]=1;
    ret[nod]=h[nod];
    stk.push_back(nod);
    for(auto e:g[nod])
    {
        if(vis[e])
        {
            ret[nod]= min(ret[nod], h[e]);
        }
        else
        {
            h[e]=h[nod]+1;
            dfs(e);
            if(ret[e]==h[nod])
            {
                //int siz=1;
                comp.push_back(veci());
                while(stk.back()!=nod)
                {
                    //siz++;
                    comp.back().push_back(stk.back());
                    stk.pop_back();
                }
                comp.back().push_back(stk.back());

                //ans+=formula(siz);
                //cerr<<stk.back()<<'\n';
                //cerr<<"am gasit comp de marime "<<siz<<'\n';
            }
            ret[nod]=min(ret[nod], ret[e]);
        }
    }
}

void solve()
{
    {
        cin>>n>>m;
        int a,b;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            pb(g[a],b);
            pb(g[b],a);
        }
    }

    dfs(1);
    cout<<comp.size()<<'\n';
    for(auto c:comp)
    {
        for(auto e:c)
        {
            cout<<e<<' ';
        }
        cout<<'\n';
    }
}

///---MAIN FUNC-------

int32_t main()
{
    IOS;
    int t=1;
    #ifdef TESTS
        cin>>t;
    #endif // TESTS
    while(t--)
    {
        solve();
    }
    return 0;
}