Cod sursa(job #916443)

Utilizator PatrikStepan Patrik Patrik Data 16 martie 2013 15:12:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 kb
    #include<cstdio>
    #include<vector>
    #include<stack>
    #include<algorithm>
    using namespace std;
    #define MAX 100001
    #define pb push_back
    #define mp make_pair
    int N , M , low[MAX] , u[MAX] , niv[MAX] ,t[MAX], l[MAX] , k , nr , start ;
    vector<int> G[MAX] ;
    vector<int> Comp[MAX];
    stack< pair<int,int> > ST;

    void citire();
    void solve();
    void DF(int nod);
    void Make_Comp(int nr,int x , int y);
    void tipar();

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        int x, y;
        freopen("biconex.in" , "r" , stdin );
        scanf("%d%d" , &N , &M );
        for( int i = 1 ; i <= M; ++i )
        {
            scanf("%d%d" , &x , &y );
            G[x].pb(y);G[y].pb(x);
        }
    }

    void solve()
    {
        for( int i = 1 ; i <= N ; ++i )
            if(!u[i])
            {
                u[i] = 1;
                niv[i] = 1;
                DF(i);
            }
    }

    void DF(int nod)
    {
        u[nod] = 1;
        low[nod] = niv[nod];
        vector<int>::iterator it;
        for( it = G[nod].begin() ; it < G[nod].end() ; ++it)
        {
            if(*it != t[nod] && niv[nod] > niv[*it])
            ST.push(mp(nod,*it));
            if(!u[*it])
            {
                niv[*it] = niv[nod]+1;
                t[*it] = nod;
                DF(*it);
                if(low[*it] >= niv[nod] && ST.size())
                    Make_Comp(++nr,nod,*it);
                if(low[*it] < low[nod])
                    low[nod] = low[*it];
            }
            else
                if(low[nod] > niv[*it] && t[nod] != *it)
                    low[nod] = niv[*it];
        }
    }

    void Make_Comp(int nr,int x , int y)
    {
        pair<int,int> M1 = mp(x,y) , M2 = mp(y,x) , M = ST.top();
        while(M != M1 && M!=M2)
        {
            Comp[nr].pb(ST.top().second);Comp[nr].pb(ST.top().first);
            ST.pop();
            M = ST.top();
        }
        Comp[nr].pb(ST.top().second);Comp[nr].pb(ST.top().first);
        ST.pop();
    }

    void tipar()
    {
        freopen("biconex.out" , "w" , stdout);
        printf("%d\n" , nr );
        vector<int>::iterator it;
        for( int i = 1 ; i <= nr ; ++i )
            {
                sort(Comp[i].begin(),Comp[i].end());
               Comp[i].erase(unique(Comp[i].begin(),Comp[i].end()),Comp[i].end());
               for(it = Comp[i].begin() ; it < Comp[i].end() ; ++it)
                printf("%d " , *it);
                printf("\n");
            }
    }