Cod sursa(job #729021)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 29 martie 2012 10:39:25
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <vector>

using namespace std;

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

struct node
{
    int nr;
    node *next;
} *v[100005], *fii[100005];
int n,m,nr,st[100005],vf,vfmax,lowlink[100005],depth[100005];
vector < vector <int> > bic;

void add(int a, int b)
{
    node *p=new node;
    p->nr=b;
    p->next=v[a];
    v[a]=p;
}

void addf(int a, int b)
{
    node *p=new node;
    p->nr=b;
    p->next=fii[a];
    fii[a]=p;
}

void cbic()
{
    ++nr;
    vector <int> comp;
    for(int i=vfmax;i>=vf-1;--i) comp.push_back(st[i]);
    vfmax=vf-1;
    bic.push_back(comp);
}

void afis()
{
    int i;
    for(i=vf;i;--i) g<<st[i]<<' ';
    g<<'\n';
}

int main()
{
    int i,j,a,b,vecin,mar;
    node *p,*q;
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>a>>b;
        add(a,b);
        add(b,a);
    }
    st[1]=1;
    vf=vfmax=1;
    depth[1]=lowlink[1]=1;
    while(vf)
    {
        i=st[vf];
        //g<<vfmax<<' ';
        //afis();
        p=v[i];
        if(p)
        {
            vecin=p->nr;
            if(depth[vecin]) lowlink[i]=min(lowlink[i],depth[vecin]);
            else
            {
                st[++vf]=vecin;
                //++vfmax;
                vfmax=max(vfmax,vf);
                depth[vecin]=lowlink[vecin]=depth[i]+1;
                addf(i,vecin);
            }
            v[i]=v[i]->next;
        }
        else
        {
            /*q=fii[i];
            while(q)
            {
                if(lowlink[q->nr]>=depth[i])
                {
                    cbic();
                }
                lowlink[i]=min(lowlink[i],lowlink[q->nr]);
                q=q->next;
            }*/
            if(lowlink[i]>=depth[st[vf-1]]) cbic();
            lowlink[st[vf-1]]=min(lowlink[i], lowlink[st[vf-1]]);
            --vf;
        }
    }
    --nr;
    //g<<"\n\n";
    g<<nr<<'\n';
    for(i=0;i<nr;++i)
    {
        mar=bic[i].size();
        for(j=0;j<mar;++j) g<<bic[i][j]<<' ';
        g<<'\n';
    }
    f.close(); g.close();
    return 0;
}