Cod sursa(job #674623)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 6 februarie 2012 16:16:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#define pb push_back
#define Nmax 100009
#define Min(a,b) ((a<b) ? a:b)

using namespace std;

int last,j,nr,n,nod2,n1,n2,m,i,x,y,lvl[Nmax],L[Nmax],ok[Nmax];
vector<int> a[Nmax],sol[Nmax];
vector<int>::iterator it;
stack<pair<int,int> > S;

void DF(int nod,int tata)
{
    ok[nod]=1;
    L[nod]=lvl[nod];

    for (vector<int>::iterator it=a[nod].begin();it!=a[nod].end();it++)
    {
        int nod2=*it;
        if (!ok[nod2])
        {
            lvl[nod2]=lvl[nod]+1;
            S.push(make_pair(nod,nod2));

            DF(nod2,nod);

            L[nod]=Min(L[nod],L[nod2]);
            if (L[nod2]>=lvl[nod])
            {
                nr++;
                do
                {
                    n1=S.top().first;
                    n2=S.top().second;
                    S.pop();
                    sol[nr].pb(n1);
                    sol[nr].pb(n2);
                } while ((n1!=nod || n2!=nod2) && (n1!=nod2 || n2!=nod));
            }
        }
        else if (nod2!=tata) L[nod]=Min(L[nod],lvl[nod2]);
    }
}


int main()
{
    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);
        a[x].pb(y);
        a[y].pb(x);
    }

    lvl[1]=1;
    DF(1,1);

    printf("%d\n",nr);
    for (i=1;i<=nr;i++)
    {
        sort(sol[i].begin(),sol[i].end());
        for (it=sol[i].begin();it!=sol[i].end();it++)
            if (it==sol[i].begin() || *it != (*(it-1))) printf("%d ",*it);
        printf("\n");
    }
}