Cod sursa(job #3001525)

Utilizator rARES_4Popa Rares rARES_4 Data 13 martie 2023 18:59:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
int lowlink[100001],indice[100001];
bool viz[100001];
stack<int>st;
int cnt,n,m;
vector<int>adiacenta[100001],rasp[100001];
void DFS(int nod,int nivel)
{
    viz[nod] = 1;
    lowlink[nod] = indice[nod] = nivel;
    st.push(nod);
    for(auto x:adiacenta[nod])
    {
        int curent = x;
        if(!viz[curent])
        {
            DFS(curent,nivel+1);

            if(lowlink[curent]>=indice[nod])
            {
              cnt++;
              while(st.top()!=curent)
              {
                rasp[cnt].push_back(st.top());
                st.pop();
              }
              rasp[cnt].push_back(st.top());
              st.pop();
              rasp[cnt].push_back(nod);
            }
            lowlink[nod] = min(lowlink[curent],lowlink[nod]);
        }
        else
        {
            lowlink[nod] = min(indice[curent],lowlink[nod]);

        }
    }
}
int main()
{
    f >> n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f >> x >> y;
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
    }
    DFS(1,1);
    g<< cnt<<'\n';
    for(int i =1;i<=cnt;i++)
    {
        for(auto x:rasp[i])
        {
            g << x<< " ";
        }
        g << endl;
    }
}