Cod sursa(job #1130710)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 28 februarie 2014 15:05:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#define vecin v[nod][j]
#define nmax 100005
using namespace std;
int n,i,j,k,x,y,level[nmax],nivel[nmax],m,rez;
vector<int>v[nmax],sol[nmax];
stack<int>s;

void adauga_componenta_biconexa(int nodx,int nody)
{
    rez++;
    while (s.top()!=nody)
    {
        sol[rez].push_back(s.top());
        s.pop();
    }
    sol[rez].push_back(nody);
    sol[rez].push_back(nodx);
    s.pop();
}

void df(int nod,int tata)
{
    nivel[nod]=nivel[tata]+1;
    level[nod]=nivel[nod];
    for (int j=0;j<v[nod].size();j++)
        if (!nivel[vecin])
        {
            s.push(vecin);
            df(vecin,nod);
            level[nod]=min(level[nod],level[vecin]);
            if (level[vecin]>=nivel[nod])
                adauga_componenta_biconexa(nod,vecin);
        }else
        if (vecin!=tata)
            level[nod]=min(level[nod],nivel[vecin]);
}

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),v[x].push_back(y),v[y].push_back(x);
    for (i=1;i<=n;i++)
        if (!nivel[i])
        {
            s.push(1);
            df(i,0);
            s.pop();
            }
    printf("%d\n",rez);
    for (i=1;i<=rez;i++)
    {
        for (j=0;j<sol[i].size();j++)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}