Cod sursa(job #581966)

Utilizator drywaterLazar Vlad drywater Data 14 aprilie 2011 19:18:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,i,x,y,nrc,st[200001][2],idx[100001],low[100001];
struct nod{int y; nod *next;};
nod *G[100001];
vector<int> C[100001];
int add(int a,int b)
{
    nod *nou=new nod;
    nou->y=b;
    nou->next=G[a];
    G[a]=nou;
    return 0;
}
int baga(int x, int y)
{
    nrc++;
    int tx,ty;
    do
    {
        tx=st[st[0][0]][0];
        ty=st[st[0][0]][1];
        st[0][0]--;
        C[nrc].push_back(tx);
        C[nrc].push_back(ty);
    }while(tx!=x || ty!=y);
    return 0;
}
int df(int vf,int pred,int index)
{
    idx[vf]=low[vf]=index;
    nod *it=new nod;
    it=G[vf];
    while (it)
    {
        if (it->y==pred) {it=it->next;continue;}
        if (idx[it->y]==-1)
        {
            st[++st[0][0]][0]=vf;
            st[st[0][0]][1]=it->y;
            df(it->y,vf,index+1);
            if (low[vf]>low[it->y]) low[vf]=low[it->y];
            if (low[it->y]>=idx[vf])
                baga(vf,it->y);
        }
        else if (low[vf]>idx[it->y]) low[vf]=idx[it->y];
        it=it->next;
    }
}
int main(void)
{
    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);
        add(x,y);
        add(y,x);
    }
    for (i=1;i<=n;i++)
    {
        idx[i]=-1;
        low[i]=0;
    }
    df(1,0,0);
    printf("%d\n",nrc);
    vector<int>::iterator it;
    for (i=1;i<=nrc;i++)
    {
        sort(C[i].begin(),C[i].end());
        C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
        for (it=C[i].begin();it!=C[i].end();it++)
        {
            printf("%d ",*it);
        }
        printf("\n");
    }
    return 0;
}