Cod sursa(job #2206268)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 21 mai 2018 23:53:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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,int y)
{
    nc++;
    while(st[ls]!=y)
    {
        cb[nc].push_back(st[ls]);
        ls--;
    }
    ls--;
    cb[nc].push_back(y);
    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,ve[x][i]);
        }
    }
       for(i=ve[x].size()-1;i>=0;i--)
       if(up[ve[x][i]]<up[x])
       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;
}