Cod sursa(job #2907442)

Utilizator maria.ianiIani Maria maria.iani Data 30 mai 2022 11:33:14
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int N,M,x,y,i,j,nrb, vizitat[nmax], stiva[nmax],varf,niv[nmax],minim[nmax];
vector<int> adj[nmax], biconexe[nmax];

void DFS(int nod, int parinte)
{
    vizitat[nod]=1;
    minim[nod]= niv[nod];
    stiva[++varf]=nod;
    for (auto nodcurent : adj[nod])
    {
        if (nodcurent==parinte) continue;
        if (vizitat[nodcurent])
            {
                minim[nod] = min(minim[nod], niv[nodcurent]);}
        else
        {
            niv[nodcurent]=niv[nod]+1;
            DFS(nodcurent, nod);
            if (minim[nodcurent]>=niv[nod])
            {
                nrb++;
                while (varf && stiva[varf]!=nodcurent)
                    biconexe[nrb].push_back(stiva[varf--]);
                biconexe[nrb].push_back(stiva[varf--]);
                biconexe[nrb].push_back(nod);
            }
            minim[nod]=min(minim[nod], minim[nodcurent]);
        }
    }
}

int main()
{
    f>>N>>M;
    for (i=1; i<=M; i++)
    {
        f>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    DFS(1,0);
    g<<nrb<<endl;

    for (i=1; i<=nrb; i++)
    {
        for (auto j:biconexe[i])
            g<<j<<" ";

        g<<endl;}
    f.close();
    g.close();
}