Cod sursa(job #1468595)

Utilizator vladttturcuman vlad vladtt Data 6 august 2015 14:30:28
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <cstring>
#include <vector>


using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int tot,n,m,i,j,x,y,tot2;

int viz[100050],nivin[100050],niv[100050],stiva[100050];

vector<int> v[100050],bi[100050];

void _cut(int poz1,int poz)
{
    bi[++tot2].push_back(stiva[poz1]);

    for(int i=poz; i<=tot; i++)
        bi[tot2].push_back(stiva[i]);
    tot=poz-1;
}

int  dfs(int ant,int nod,int s)
{
    viz[nod]=1;

    nivin[nod]=s;

    niv[nod]=s;


    int poz=++tot;

    stiva[poz]=nod;


    for(int i=0; i<v[nod].size(); i++)
    {
        int b=v[nod][i];

        if(viz[b]==1)
        {
            if(b!=ant)
                niv[nod]= niv[nod] > nivin[b] ? nivin[b] : niv[nod];
        }
        else
        {
            int ctot=tot+1;
            int x=dfs(nod,b,s+1);


            if(x>=niv[nod] )
                _cut(poz,ctot);

            niv[nod]=niv[nod] > x ? x : niv[nod];


        }
    }



    return niv[nod];

}


int main()
{

    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(0,1,1);

 if(tot!=1)
    {
    fout<<tot2+1<<'\n';




        for(j=1; j<=tot; j++)
            fout<<stiva[j]<<' ';
        fout<<'\n';
    }
    else
        fout<<tot2<<'\n';

    for(i=1; i<=tot2; i++)
    {
        if(bi[i].size()>1)
        {
            for(j=0; j<bi[i].size(); j++)
                fout<<bi[i][j]<<' ';
            fout<<'\n';
        }
    }

    return 0;
}