Cod sursa(job #1468543)

Utilizator vladttturcuman vlad vladtt Data 6 august 2015 12:46:53
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 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;

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

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

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

    nivin[nod]=s;

    niv[nod]=s;

    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 x=dfs(nod,b,s+1);
            niv[nod]=niv[nod] > x ? x : niv[nod];

        }
    }

    return niv[nod];

}

int dfs2(int nod,int s)
{
    bi[s].push_back(nod);

    viz[nod]=1;

    for(int i=0; i<v[nod].size(); i++)
    {
        int b=v[nod][i];
        if(viz[b]==0)
        {
            if(niv[nod]==niv[b])
            {
                dfs2(b,s);
            }
            else
            {
                bi[++tot].push_back(nod);
                bi[tot].push_back(b);

                if(v[b].size()!=1)
                    dfs2(b,++tot);
            }
        }
    }

    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);

    memset(viz,0,sizeof(viz));

    tot=1;

    dfs2(1,1);

    fout<<tot<<'\n';

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

    return 0;
}