Cod sursa(job #2754445)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 25 mai 2021 20:47:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
const int dim=1e5+10;
int n,m,cnt;
vector < int > V[dim],lvl(dim,0),low(dim),A[dim];
vector < bool > viz(dim,0);

stack < int > S;

void Biconex(int nod,int nvl)
{
    viz[nod]=1;
    lvl[nod]=nvl;
    low[nod]=nvl-1;
    S.push(nod);

    for(int vecin:V[nod])
    {
        if(!viz[vecin])
        {
            Biconex(vecin,nvl+1);
            low[nod]=min(low[nod],low[vecin]);

            if(low[vecin]>=lvl[nod])
            {
                while(S.top()!=vecin)
                {
                    A[cnt].pb(S.top());
                    S.pop();
                }
                S.pop();
                A[cnt].pb(vecin);
                A[cnt].pb(nod);
                cnt++;
            }
        }
        else
            low[nod]=min(low[nod],lvl[vecin]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        f>>a>>b;
        V[a].pb(b);
        V[b].pb(a);
    }
    Biconex(1,1);
//for(int i=1;i<=n;i++)
   //cout<<i<<' '<<low[i]<<' '<<lvl[i]<<'\n';
    g<<cnt<<'\n';
    for(int i=0;i<cnt;i++)
    {
        for(int j:A[i]) g<<j<<' ';
        g<<'\n';
    }

    return 0;
}