Cod sursa(job #1314367)

Utilizator maribMarilena Bescuca marib Data 11 ianuarie 2015 19:56:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <list>
#include <stack>
#define DIM 100001
#include <queue>

using namespace std;

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

int biconex, bicon[DIM], dad[DIM], idx[DIM], lowl[DIM];

int index, n, m, a, b;

stack < pair<int, int> > stk;

queue <int> q;

list <int> nod[DIM];

void build(int x, int y)
{
    int v1, v2, ok=0;
    biconex++;
    do
    {
        v1=stk.top().first;
        v2=stk.top().second;
        if((v1==x&&v2==y)||(v1==y&&v2==x))
        {
            ok=1;
        }
        if(bicon[v1]!=biconex)
        {
            q.push(v1);
            bicon[v1]=biconex;
        }
        if(bicon[v2]!=biconex)
        {
            q.push(v2);
            bicon[v2]=biconex;
        }
        stk.pop();
    }while(ok==0);
    //stk.push(make_pair(x, y));
    q.push(0);
}

void tarjan(int vf)
{
    idx[vf]=(++index);
    lowl[vf]=index;
    for( list <int>::iterator j=nod[vf].begin(); j!=nod[vf].end(); ++j)
    {
        if(idx[*j]==0)
        {
            dad[*j]=vf;
            stk.push(make_pair(vf, *j));
            tarjan(*j);
            lowl[vf]=min(lowl[vf], lowl[*j]);
            if(lowl[*j]>=idx[vf])
                build(*j, vf);
        }
        else
        {
            if(dad[vf]!=(*j))
            {
                //if(idx[*j]<lowl[vf])
                    //stk.push(make_pair(vf, (*j)));
                lowl[vf]=min(lowl[vf], idx[*j]);
            }
        }
    }
}

int main()
{
    in>>n>>m;
    while(m--)
    {
        in>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
    for(int i=1; i<=n; ++i)
    {
        if(idx[i]==0)
        {
            index=0;
            tarjan(i);
        }
    }
    out<<biconex<<"\n";
    while(!q.empty())
    {
        a=q.front();
        if(a!=0)
            out<<a<<" ";
        else out<<"\n";
        q.pop();
    }
    in.close();
    out.close();
    return 0;
}