Cod sursa(job #433807)

Utilizator hasegandaniHasegan Daniel hasegandani Data 4 aprilie 2010 13:50:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<set>

using namespace std;

#define Nmax 100010
#define Mmax 200010
#define fs first
#define sc second
#define mp make_pair

int N,v[Nmax],t[Nmax],niv[Nmax],lv[Nmax];
vector <int> l[Nmax];
stack < pair<int,int> > st;
vector < set<int> > comp;

void afis_stiva()
{
    printf("st:\n");
    stack < pair<int,int> > st2;
    for(; !st.empty() ;)
        {
        st2.push(st.top());
        st.pop();
        }
    pair<int,int> x;
    for(; !st2.empty() ;)
        {
        x=st2.top();
        printf("%d %d\n",x.fs,x.sc);
        st.push(st2.top());
        st2.pop();
        }
    printf("gata stiva\n");
}

void rezolv(int x,int y)
{
    set<int> s;
    pair<int,int> vf;
    for( vf=st.top() ; vf.fs != x || vf.sc !=y ; vf=st.top())
        {
        s.insert(vf.fs);
        s.insert(vf.sc);
        st.pop();
        }
    s.insert(x);
    s.insert(y);
    comp.push_back( s );
    st.pop();
}

void DF(int k,int level,int tata)
{
    v[k]=1;
    t[k]=tata;
    niv[k]=lv[k]=level;

    vector<int>::iterator it;
    for(it=(l[k]).begin();it!=(l[k]).end();++it)
        if ((*it)!=t[k])
            {
            if (!v[*it])
                {
                st.push( mp(k,*it) );
                DF( *it , level+1 , k);
                if (lv[*it] >= niv[k])
                    rezolv(k,*it);
                }
            lv[k] = min(lv[k],lv[*it]);
            }
}

void afis()
{
    printf("%d\n",comp.size());
    set<int>::iterator it;
    for(int i=0;i<(int)comp.size();++i)
        {
        for(it=comp[i].begin(); it!=comp[i].end() ;++it)
            printf("%d ",(*it));
        printf("\n");
        }
}

void cit();

int main()
{
    cit();
    DF(1,0,0);
    afis();
    return 0;
}

void cit()
{
    int a,b,M;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d%d",&a,&b);
        l[a].push_back(b);
        l[b].push_back(a);
        }
}