Cod sursa(job #1413329)

Utilizator zpaePopescu Andreea zpae Data 1 aprilie 2015 20:09:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <vector>
#define N 100005
using namespace std;
vector<int>v[N],h[N],q;
int l[N],f[N],k,n,s;

void sol(int x, int y)
{
    s++;
    while(y!=q.back())
    {
        h[s].push_back(q.back());
        q.pop_back();
    }
    q.pop_back();
    h[s].push_back(y);
    h[s].push_back(x);
}

void df(int x, int t)
{
    int i;
    f[x]=l[x]=++k;
    for(i=0;i<v[x].size();i++)
    {
        if(v[x][i]==t)
            continue;
        if(f[v[x][i]])
        {
            l[x]=min(l[x],f[v[x][i]]);
            continue;
        }
        q.push_back(v[x][i]);
        df(v[x][i],x);
        l[x]=min(l[x],l[v[x][i]]);
        if(l[v[x][i]]>=f[x])
            sol(x, v[x][i]);
    }

}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int m,i,j,x,y;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    df(1,0);
    printf("%d\n",s);
    for(i=1;i<=s;i++)
    {
        for(j=0;j<h[i].size();j++)
            printf("%d ",h[i][j]);
        printf("\n");
    }
    return 0;
}