Cod sursa(job #1119412)

Utilizator PatrikStepan Patrik Patrik Data 24 februarie 2014 17:37:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
    #include<cstdio>
    #include<vector>
    #include<set>
    #include<cstring>
    using namespace std;
    #define MAX  100001
    #define pb push_back
    int N , M , f[MAX]  , k , t ;
    vector<int> G[MAX] , Gt[MAX] , C[MAX];
    struct comp{
        bool operator()(int a , int b)
        {
            return f[a] > f[b];
        }
    };
    multiset<int,comp> Q;
    bool u[MAX];


    void read();
    void DFS(int nod);
    void DFST(int nod);
    void write();
    void solve();

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

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

    void solve()
    {
        for(int i = 1 ; i<= N ; ++i )
            if(!u[i])DFS(i);
        for(int i = 1 ; i <= N ; ++i )Q.insert(i);
        memset(u,0,sizeof(u));
        while(!Q.empty())
        {
            int nod = *Q.begin();
            Q.erase(Q.begin());
            if(!u[nod])
            {
                k++;
                DFST(nod);
            }
        }
    }

    void DFS(int nod)
    {
        t++;
        u[nod] = 1;
        for(int i = 0 ;  i<(int)G[nod].size() ; ++ i)
            if(!u[G[nod][i]])
            DFS(G[nod][i]),t++;
        f[nod] = t;
    }

    void DFST(int nod)
    {
        C[k].pb(nod);
        u[nod] = 1;
        for(int i = 0 ;i < (int)Gt[nod].size() ; ++i )
            if(!u[Gt[nod][i]])
            DFST(Gt[nod][i]);
    }

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