Cod sursa(job #1119929)

Utilizator PatrikStepan Patrik Patrik Data 24 februarie 2014 20:48:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
    #include<cstdio>
    #include<vector>
    #include<stack>
    using namespace std;
    #define MAX 100001
    #define pb push_back
    #define mp make_pair
    #define PII pair<int,int>
    #define x first
    #define y second
    int N , M  , k , niv[MAX] , low[MAX] , t[MAX] , viz[MAX];
    vector<int> G[MAX] , Comp[MAX];
    stack<PII> st;

    void read();
    void solve();
    void write();
    void DF(int nod);
    void Make_comp(int k , int x , int y);


    int main()
    {
        read();
        solve();
        write();
        return 0;
    }


    void read()
    {
        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(!niv[i])
        {
            niv[i] = 1;
            DF(i);
        }
    }

    void DF(int nod)
    {
        low[nod] = niv[nod];
        for(int i = 0 ; i< (int)G[nod].size() ; ++i )
        {
            if(!niv[G[nod][i]])
            {
                t[G[nod][i]] = nod;
                niv[G[nod][i]] = niv[nod] +1;
                st.push(mp(nod,G[nod][i]));
                DF(G[nod][i]);
                if(low[G[nod][i]] < low[nod])
                    low[nod] = low[G[nod][i]];
                if(low[G[nod][i]] >= niv[nod])
                    Make_comp(++k,nod,G[nod][i]);
            }
            else
                if(G[nod][i] != t[nod] && low[G[nod][i]] <  low[nod])
                    low[nod] = low[G[nod][i]];
        }
    }

    void Make_comp(int k , int x , int y)
    {
        PII m;
        do
        {
            m = st.top();
            st.pop();
            if(viz[m.x] != k)
            {
                viz[m.x] = k;
                Comp[k].pb(m.x);
            }
            if(viz[m.y] != k)
            {
                viz[m.y] = k;
                Comp[k].pb(m.y);
            }
        }while(m.x != x  && m.y != y);
    }

    void write()
    {
        freopen("biconex.out" , "w"  , stdout );
        printf("%d\n" , k);
        for(int i = 1 ; i <= k ; ++i )
        {
            for(int j = 0 ; j <(int)Comp[i].size() ; ++j )
                printf("%d " , Comp[i][j]);
            printf("\n");
        }
    }