Cod sursa(job #1529466)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 20 noiembrie 2015 22:22:52
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#define MAX_N 100001
using namespace std;
vector<int> ve[MAX_N+5],cb[200005];
int lv[MAX_N+5],st[MAX_N+5],up[MAX_N+5],ls,nc;
void baga(int x)
{
    nc++;
    while(st[ls]!=x)
    {
        cb[nc].push_back(st[ls]);
        ls--;
    }
    cb[nc].push_back(x);
}
void dfs(int x)
{
        up[x]=lv[x];
    int i,j;
    ls++;
    st[ls]=x;
    for(i=ve[x].size()-1;i>=0;i--)
    {
        if(lv[ve[x][i]]==0)
        {
            lv[ve[x][i]]=lv[x]+1;
            dfs(ve[x][i]);
            if(up[ve[x][i]]>=lv[x])
            baga(x);
        }
    }
       for(i=ve[x].size()-1;i>=0;i--)
       if(up[ve[x][i]]<up[x] && up[ve[x][i]]!=0)
       up[x]=up[ve[x][i]];
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m,i,j,x,y,lu;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ve[x].push_back(y);
        ve[y].push_back(x);
    }
    lv[1]=1;
    ls=0;
    nc=0;
    dfs(1);
    printf("%d\n",nc);
    for(i=1;i<=nc;i++)
    {
    sort(cb[i].begin(),cb[i].end());
    lu=cb[i].size();
    for(j=0;j<lu;j++)
    printf("%d ",cb[i][j]);
    printf("\n");
    }
    return 0;
}