Cod sursa(job #2765253)

Utilizator CelestinNegraru Celestin Celestin Data 26 iulie 2021 00:24:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_set>
#include <algorithm>
#define maxi 1e+5
using namespace std;
using int32=int;
using booly=bool;
ifstream cin;
ofstream cout;
unordered_set<int> S;
vector<int32> V[1+(int)maxi];
vector<int32> SOL[1+(int)maxi];
vector<int32>::iterator I1,I2;
stack<int32> stiva;
booly viz[1+(int32)maxi];
int32 tata[1+(int32)maxi],lvl[1+(int32)maxi],nma[1+(int32)maxi],n,m,cnt;
void READ()
{
    int a,b;
    cin.open("biconex.in",ios::in);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    cin.close();
    return;
}
void DFS(int x)
{
    stiva.push(x);
    viz[x]=true;
    nma[x]=lvl[x];
    for(auto a:V[x])
    {
        if(viz[a]&&tata[x]!=a)///stramos in app
        {
            if(lvl[a]<nma[x])
                nma[x]=lvl[a];
        }
        if(!viz[a])
        {
            tata[a]=x;
            lvl[a]=lvl[x]+1;
            DFS(a);
            if(nma[a]<nma[x])
                nma[x]=nma[a];
            if(lvl[x]<=nma[a]&&tata[a]==x)
            {S.insert(x);
             cnt++;
             while(stiva.top()!=a)
             {
                 SOL[cnt].push_back(stiva.top());
                 stiva.pop();
             }
             SOL[cnt].push_back(a);
             stiva.pop();
             SOL[cnt].push_back(x);
            }
        }
    }
}
int main()
{
    cout.open("biconex.out",ios::out);
    READ();
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            lvl[i]=1;
            nma[i]=1;
            DFS(i);
        }
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
    {
        I1=SOL[i].begin();
        I2=SOL[i].end();
        sort(I1,I2);
    }
    for(int i=1;i<=cnt;i++)
    {
        for(auto a:SOL[i])
            cout<<a<<" ";
        cout<<'\n';
    }
    cout.close();
    return 0;
}