Cod sursa(job #2559445)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 27 februarie 2020 12:29:27
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;
int niv[100001],nmina[100001],f[100001],bif[100001];
vector <int> G[100001],steve,art;
vector < vector <int> > rez;
vector <pair <int,int>> critic;
void dfs(int i,int tata)
{
    int num=0,pct=0;
    niv[i]=niv[tata]+1;
    nmina[i]=niv[i];
    f[i]=1;
    steve.push_back(i);
    for(auto it : G[i])
        if(it!=tata)
            if(!f[it])
            {
                num++;
                dfs(it,i);
                if(nmina[it]<nmina[i])
                    nmina[i]=nmina[it];
                if(niv[i]<=nmina[it] && i!=1 && !bif[i])
                {
                    bif[i]=1;
                    art.push_back(i);
                }
                if(niv[i]<nmina[it])
                    critic.push_back({i,it});
                if(niv[i]<=nmina[it])
                {
                    vector <int> aux;
                    while(steve.back()!=it)
                    {
                        aux.push_back(steve.back());
                        steve.pop_back();
                    }
                    aux.push_back(steve.back());
                    steve.pop_back();
                    aux.push_back(i);
                    rez.push_back(aux);
                }
            }
            else
                if(nmina[i]>niv[it])
                    nmina[i]=niv[it];
    if(i==1 && num>1)
        art.push_back(1);

}
int main()
{
    int q,n,m,x,y,i,j;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    //scanf("%d",&q);
    q=1;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    niv[1]=nmina[1]=1;
    dfs(1,0);
    if(q==1)
    {
        //printf("%d\n",rez.size());
        for(i=0; i<rez.size(); i++)
        {
            printf("%d ",rez[i].size());
            for(j=0; j<rez[i].size(); j++)
                printf("%d ",rez[i][j]);
            printf("\n");
        }
        return 0;
    }
    if(q==2)
    {
        printf("%d\n",art.size());
        for(auto it : art)
            printf("%d ",it);
        return 0;
    }
    printf("%d\n",critic.size());
    for(auto it : critic)
        printf("%d %d\n",it.first,it.second);

    return 0;
}