Cod sursa(job #1231154)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 19 septembrie 2014 18:59:15
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <vector>
#include <set>
#define N 100010
using namespace std;
int niv[N],up[N],x[N],y[N],X,Y,k,n,m,i,sol;
vector<int>v[N],st;
set<int>s;
vector<set<int> >Q;
void df(int nod,int tata)
{
    niv[nod]=up[nod]=niv[tata]+1;
    int vecin;
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
    {
        vecin=x[*it]+y[*it]-nod;
        if(vecin==tata)continue;
        if(!niv[vecin])
        {
            st.push_back(x[*it]);
            st.push_back(y[*it]);
            df(vecin,nod);
            up[nod]=min(up[nod],up[vecin]);
            if(up[vecin]>=niv[nod])
            {
                sol++;
                s.clear();
                for(;;)
                {
                    Y=st.back();
                    st.pop_back();
                    X=st.back();
                    st.pop_back();
                    s.insert(X);
                    s.insert(Y);
                    if(X==x[*it]&&Y==y[*it])break;
                }
                Q.push_back(s);
            }
        }
        else
            up[nod]=min(up[vecin],up[nod]);
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d",&x[m],&y[m]);
        v[x[m]].push_back(m);
        v[y[m]].push_back(m);
    }
    for(i=1;i<=n;i++)
        if(!niv[i])
            df(i,0);
    //sol=Q.size();
    printf("%d\n",sol);
    for(i=0;i<sol;i++)
    {
        for(set<int>::iterator it=Q[i].begin();it!=Q[i].end();it++)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}