Cod sursa(job #600545)

Utilizator nervousNervous nervous Data 2 iulie 2011 11:52:40
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.28 kb
#include <fstream>
#include <cstring>

#define X1 100001

using namespace std;

ifstream in;
ofstream out;

struct graf
{
    int nod;
    graf *link;
}*v[X1];

struct sol
{
    int nod;
    sol *link;
}*biconex[X1];

struct stack
{
    int x,y;
}st[X1];

int T[X1],level[X1],low[X1];
char use[X1];

int size=0,cnt=0;

inline void add(int x,int y)
{
    graf *p;

    p=new graf;
    p->nod=y;
    p->link=v[x];
    v[x]=p;
}

inline void addsol(int x,int y)
{
    sol *p;

    p=new sol;
    p->nod=y;
    p->link=biconex[x];
    biconex[x]=p;
}

inline void df(int nod)
{
    graf *p;
    int x,y;

    use[nod]=1;
    p=v[nod];

    for(;p!=NULL;p=p->link)
    {
        if(T[nod]!=p->nod&&level[nod]>=level[p->nod])
        {
            st[++size].x=nod;
            st[size].y=p->nod;
        }
        if(use[p->nod]==0)
        {
            T[p->nod]=nod;
            level[p->nod]=level[nod]+1;
            low[p->nod]=level[p->nod];
            df(p->nod);
            if(low[p->nod]<low[nod]) low[nod]=low[p->nod];
            if(low[p->nod]>=level[nod])
            {
                ++cnt;
                if(size)
                    do
                    {
                        x=st[size].x;
                        y=st[size].y;
                        if(T[x]==y) addsol(cnt,x);
                        else
                        if(T[y]==x) addsol(cnt,y);
                        --size;
                    }
                    while((x!=nod||y!=p->nod)&&(x!=p->nod||y!=nod)&&size);
                addsol(cnt,nod);
            }
        }
        else
        if(T[nod]!=p->nod&&low[nod]>level[p->nod])
            low[nod]=level[p->nod];
    }
}

int main()
{
    int M,N,x,y;

    in.open("biconex.in");
    in>>N>>M;
    for(;M;--M)
    {
        in>>x>>y;
        add(x,y);
        add(y,x);
    }
    in.close();

    memset(T,0,sizeof(T));
    memset(use,0,sizeof(use));
    memset(low,0,sizeof(low));
    memset(level,0,sizeof(level));

    df(1);

    out.open("biconex.out");
    out<<cnt<<'\n';
    for(int i=1;i<=cnt;++i)
    {
        for(sol *p=biconex[i];p!=NULL;p=p->link)
            out<<p->nod<<' ';
        out<<'\n';
    }
    out.close();

    return 0;
}