Cod sursa(job #402584)

Utilizator RobybrasovRobert Hangu Robybrasov Data 23 februarie 2010 23:04:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#define N 100005
#define M 200005

using namespace std;

vector<int> L[N];
stack< pair<int, int > > S;
set<int> rez[M];
int tata[N],E[N],jos[N],niv[N],ind[M];
int kont=0,crit=0;

void dfs(int nod)
{
    E[nod]=1;
    int MIN=niv[nod]; //nivelul lui

    for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
    {
        if (!E[*it])
        {
            tata[*it]=nod;
            niv[*it]=niv[nod]+1;
            dfs(*it);

            //minimul valorilor fiilor lui
            if (jos[*it]<MIN)
                MIN=jos[*it];
        }

        //muchia de intoarcere
        if (E[*it] && niv[*it]<niv[nod] && tata[nod]!=*it && niv[*it]<MIN)
            MIN=niv[*it];
    }

    jos[nod]=MIN;
}

void biconex(int nod)
{
    E[nod]=1;
    for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
        if (tata[nod]!=*it)
        {
            //muchia de intoarcere
            if (E[*it] && niv[*it]<niv[nod]) S.push(make_pair(nod,*it));

            if (!E[*it])
            {
                S.push(make_pair(nod,*it));
                biconex(*it);

                //a gasit un nod critic - scoate din stiva
                if ((jos[*it]>=niv[nod] && nod!=1) || (nod==1 && crit))
                {
                    kont++;
                    for (; S.top().first!=nod || S.top().second!=*it; S.pop())
                    {

                        rez[kont].insert(S.top().first);
                        rez[kont].insert(S.top().second);
                    }
                    rez[kont].insert(S.top().first);
                    rez[kont].insert(S.top().second);
                    S.pop();
                }
            }
        }
}

int main()
{
    int n,m;
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        L[x].push_back(y);
        L[y].push_back(x);
    }
    niv[1]=1;
    jos[1]=1;
    dfs(1);

    //se uita daca radacina e nod critic
    int root=0;
    for (vector<int>::iterator it=L[1].begin(); it!=L[1].end(); it++)
        if (tata[*it]==1) root++;
    if (root>1) crit=1;

    memset(E,0,sizeof(E));
    biconex(1);

    if (!S.empty())
    {
        kont++;
        for (; !S.empty(); S.pop())
        {
            rez[kont].insert(S.top().first);
            rez[kont].insert(S.top().second);
        }
    }

    printf("%d\n",kont);
    for (int i=1; i<=kont; i++, printf("\n"))
        for (set<int>::iterator it=rez[i].begin(); it!=rez[i].end(); it++)
            printf("%d ",*it);

    return 0;
}