Cod sursa(job #2999593)

Utilizator AndreiStreheStreche Andrei Claudiu AndreiStrehe Data 11 martie 2023 10:44:27
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

#define nmax 100001

vector <int> a[nmax];
vector <int> sol[nmax];

int i,j,nod,vecin,nrs,n,m,k1,k2,k;
bool viz[nmax];
int d[nmax],minim[nmax],st[nmax];

int dfs(int nod, int niv, int tata)
{
    viz[nod]=1;
    d[nod]=niv;
    minim[nod]=niv;
    st[++k]=nod;

    for(unsigned int i=0;i<a[nod].size();i++)
    {
        int vecin=a[nod][i];
        if(viz[vecin]==0 && vecin!=tata)
        {
            dfs(vecin,niv+1,nod);
            minim[nod]=min(minim[nod], minim[vecin]);

            if(d[nod]<=minim[vecin] && vecin!=nod)
            {
                nrs++;
                while(st[k]!=nod && k>0)
                {
                    sol[nrs].push_back(st[k]);
                    k--;
                }
                sol[nrs].push_back(st[k]);
            }
        }
        else if(vecin!=tata)
            minim[nod]=min(minim[nod],d[vecin]);
    }
}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>k1>>k2;

        a[k1].push_back(k2);
        a[k2].push_back(k1);
    }


    for(i=1;i<=n;i++)
    {
        sort(a[i].begin(), a[i].end());
    }
    dfs(1,1,0);

    g<<nrs<<'\n';
    for(i=1;i<=nrs;i++)
    {
        for(j=0;j<sol[i].size();j++)
            g<<sol[i][j]<<" ";
        g<<endl;
    }

    return 0;
}