Cod sursa(job #916418)

Utilizator PatrikStepan Patrik Patrik Data 16 martie 2013 14:38:10
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
    #include<cstdio>
    #include<vector>
    #include<stack>
    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] , 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 critic);
    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);
                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 critic)
    {
        start = ST.top().second;
        while(ST.size())
        {
            Comp[nr].pb(ST.top().second);
            if(ST.top().first == critic)
            {
                if(critic != start)
                    Comp[nr].pb(ST.top().first);
                ST.pop();
                break;
            }
            ST.pop();
        }
    }

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