Cod sursa(job #2801005)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 14 noiembrie 2021 17:31:35
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("3max.in");
ofstream g("3max.out");

const int NMAX=100001;
vector<int>G[NMAX],CB[NMAX];
int N,M,
    nrCB,
    Niv[NMAX],Nma[NMAX],
    S[NMAX],vf;
bool viz[NMAX];

void citire()
{
    int x,y;
    cin>>N>>M;
    for(int i=1;i<=M;i++){
     cin>>x>>y;
     G[x].push_back(y);
     G[y].push_back(x);
    }
}

void DFS(int x,int tata)
{
    S[++vf]=x;
    viz[x]=1;
    Niv[x]=Niv[tata]+1;
    Nma[x]=Niv[x];
    for(auto &y : G[x])
    {
       if(y==tata) continue;
       if(viz[y])
           Nma[x]=min(Nma[x],Niv[y]);
       else
       {
           DFS(y,x);
           Nma[x]=min(Nma[x],Nma[y]);
           //
           if(Niv[x]<=Nma[y])
           {
             ++nrCB;
             while(S[vf]!=y)
                CB[nrCB].push_back(S[vf--]);
             CB[nrCB].push_back(y);
             --vf;
             CB[nrCB].push_back(x);
           }
       }
    }
}

int main()
{
 citire();
 DFS(1,0);
 cout<<nrCB<<'\n';
 for(int i=1;i<=nrCB;i++)
 {
    for(auto &x : CB[i])
      cout<<x<<' ';
    cout<<'\n';
 }
 return 0;
}