Cod sursa(job #2715523)

Utilizator vlasdumitruVlas Dumitru vlasdumitru Data 3 martie 2021 19:34:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.39 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int p,afis,n,m,nush[100005],nivel[100005],nma[100005],stiva[100005],niv=0,rad,nr,nr11;
int nr1;
int afis2[100005],nr2;
int afis3[100005][3],nr3;
vector < int > afis1[100005];
struct nod
{
    int info;
    nod *urm;
};
nod *v[100005];
void adaug(int i,int j)
{
    nod *q;
    q=new nod;
    q->info=j;
    q->urm=v[i];
    v[i]=q;
}
void citire()
{
    int i,j;
    fin>>n>>m;
    while (m!=0)
    {
        fin>>i>>j;
        adaug(i,j);
        adaug(j,i);
        m--;
    }
}
void DFS(int k,int tata)
{
    int x,nr=0;
    nod *q;
    nush[k]=1;
    stiva[++niv]=k;
    nivel[k]=nivel[tata]+1;
    nma[k]=nivel[k];
    q=v[k];

    while (q!=NULL)
    {
        x=q->info;
        if (x!=tata)
        {
            if (nush[x]==1)
            {
                if (nma[k]>nivel[x])
                    nma[k]=nivel[x];
            }
            else
            {
                nr++;
                DFS(x,k);
                if (nma[k]>nma[x])
                    nma[k]=nma[x];
                if (p==1)
                {
                    if (nivel[k]<=nma[x])
                    {
                        nr1++;
                        while(stiva[niv]!=x)
                        {
                            afis1[nr1].push_back(stiva[niv]);
                            niv--;
                        }
                        afis1[nr1].push_back(x);
                        niv--;
                        afis1[nr1].push_back(k);

                        ///niv--;
                    }
                }
                if (p==2)
                {
                    if (nivel[k]<=nma[x] and k!=rad)
                    {
                        afis2[k]=1;
                    }
                }
                if (p==3)
                {
                    if (nivel[k]<nma[x])
                    {
                        ///fout<<k<<" "<<x<<'\n';
                        nr3++;
                        afis3[nr3][1]=k;
                        afis3[nr3][2]=x;
                    }
                }
            }
        }
        q=q->urm;
    }
    if (k==rad and nr>1)
    {
        afis2[k]=1;
    }
}
int main()
{
    int i,j;
    ///fin>>p;
    citire();
    p=1;
    for (i=1;i<=n;i++)
    {
        if (nush[i]==0)
        {
            rad=i;
            DFS(i,0);
        }
    }
    if (p==1)
    {
        fout<<nr1<<'\n';
        for (i=1;i<=nr1;i++)
        {
            nr11=afis1[i].size();
            ///fout<<nr11<<" ";
            for (j=0;j<nr11;j++)
                fout<<afis1[i][j]<<" ";
            fout<<'\n';
        }
    }
    if (p==2)
    {
        nr2=0;
        for (i=1;i<=n;i++)
            if (afis2[i]==1)
                nr2++;
        fout<<nr2<<'\n';
        for (i=1;i<=n;i++)
            if (afis2[i]==1)
                fout<<i<<" ";
    }
    if (p==3)
    {
        fout<<nr3<<'\n';
        for (i=1;i<=nr3;i++)
            fout<<afis3[i][1]<<" "<<afis3[i][2]<<'\n';
    }
   /// fout<<afis<<'\n';
    /*for (i=1; i<=n; i++)
        fout<<i<<" ";
    fout<<'\n';
    for (i=1; i<=n; i++)
        fout<<nivel[i]<<" ";
    fout<<'\n';
    for (i=1; i<=n; i++)
        fout<<nma[i]<<" ";*/
    return 0;
}