Cod sursa(job #1125151)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 26 februarie 2014 15:58:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#define NMax 100005
using namespace std;

int crt,comp=0,N,M,dfn[NMax],low[NMax];
set<int> bic[NMax];
stack<pair<int,int> > S;
vector<int> vc[NMax];

void comp_bicon (int x, int y)
{
    comp++;
    while (S.top().first!=x || S.top().second!=y)
    {
        bic[comp].insert(S.top().first);
        bic[comp].insert(S.top().second);
        S.pop();
    }
    bic[comp].insert(S.top().first);
    bic[comp].insert(S.top().second);
    S.pop();
}

void biconex (int prec, int nod)
{
    int i,fiu;
    dfn[nod]=low[nod]=++crt;
    for (i=0; i<vc[nod].size(); i++)
    {
        fiu=vc[nod][i];
        if (fiu!=prec && dfn[fiu]<dfn[nod])
            S.push(make_pair(nod,fiu));
        if (dfn[fiu]==-1)
        {
            biconex(nod,fiu);
            low[nod]=min(low[nod],low[fiu]);
            if (low[fiu]>=dfn[nod])
                comp_bicon(nod,fiu);
        }
        else if (fiu!=prec)
            low[nod]=min(low[nod],dfn[fiu]);
    }
}

int main ()
{
    int i,x,y;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d",&x,&y);
        vc[x].push_back(y);
        vc[y].push_back(x);
    }
    for (i=1; i<=N; i++)
        dfn[i]=low[i]=-1;
    S.push(make_pair(-1,1));
    biconex(-1,1);
    printf("%d\n",comp);
    for (i=1; i<=comp; i++, printf("\n"))
        for (set<int>::iterator it=bic[i].begin(); it!=bic[i].end(); ++it)
            printf("%d ",*it);
    return 0;
}