Cod sursa(job #903114)

Utilizator PatrikStepan Patrik Patrik Data 1 martie 2013 18:35:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
    #include<cstdio>
    #include<fstream>
    #include<vector>
    #include<set>
    #define MAX 100005
    #define pb push_back
    using namespace std;
    int N ,M  , nr  , tf[MAX] , fin , l[MAX] , sol[MAX] , pas  , k;
    bool viz[MAX];
    vector<int> G[MAX] , GT[MAX];
    struct cmp{bool operator()(int x , int y){return tf[x] > tf[y];}};
    multiset<int,cmp> Q;

    void citire();
    void solve();
    void DF(int nod);
    void DFT(int nod);
    void tipar();

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

    void citire()
    {
        int x , y;
        ifstream f("ctc.in");
        f>>N>>M;
        for(int i = 1 ; i <= M ; ++i )
        {
            f>>x>>y;
            G[x].pb(y);
            GT[y].pb(x);
        }
        f.close();
    }

    void solve()
    {
        for( int i = 1 ; i <= N ; ++i )
            if(!viz[i])DF(i);
        for(int i = 1 ; i <= N ; ++i )Q.insert(i);
        for(int i = 1 ; i <=N ; ++i )viz[i] = 0;
        while(!Q.empty())
        {
            if(viz[*Q.begin()])
                Q.erase(Q.begin());
            else
            {
                DFT(*Q.begin());
                sol[++sol[0]] = k;
            }
        }
    }

    void DF(int nod)
    {
        pas++;
        viz[nod] = 1;
        for( int i = 0 ; i < G[nod].size() ; ++i )
            if(!viz[G[nod][i]])
                DF(G[nod][i]),pas++;
        tf[nod] = pas;
    }

    void DFT(int nod)
    {
        viz[nod] = 1;
        for(int i = 0 ; i < GT[nod].size() ; ++i )
            if(!viz[GT[nod][i]])
                DFT(GT[nod][i]);
        l[++k] = nod;
    }

    void tipar()
    {
        ofstream g("ctc.out");
        g<<sol[0]<<"\n";
        for(int i = 1 ; i <= sol[0] ; ++i )
        {
            int j;
            for(j = (i==1 )? 1 : sol[i-1] + 1 ; j <= sol[i] ; ++j )
                g<<l[j]<<" ";
            g<<"\n";
        }
        /*for( int i =  1 ; i <= N ; ++i)
        {
            for(int j = 0 ; j < GT[i].size()  ; ++j )
                g<<GT[i][j]<<" ";
            g<<"\n";
        }*/
        g.close();
    }