Cod sursa(job #923783)

Utilizator superman_01Avramescu Cristian superman_01 Data 23 martie 2013 20:40:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb

//CTC with kosaraju' algorithm

#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>

#define MAX_N 100005

FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");

using namespace std;

vector <int> G[MAX_N],GT[MAX_N],sol[MAX_N];
stack <int> S;
int n,m,ctc;
bool used[MAX_N],used_ctc[MAX_N];

void read ( void )
{
    fscanf(f,"%d%d",&n,&m);
    for(int i(1);  i <= m ; ++i )
    {
        int a,b;
        fscanf(f,"%d%d",&a,&b);
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    fclose(f);

}
void DFP( int node )
{
    vector<int>::iterator it;
    used[node]=true;
    for(it=G[node].begin(); it!=G[node].end(); ++it)
        if(!used[*it])
        DFP(*it);

    S.push(node);
}
void DFM(int node )
{
    vector <int> ::iterator it;

    used_ctc[node]=true;

    for(it=GT[node].begin(); it!=GT[node].end() ; ++it )
        if(!used_ctc[*it])
             DFM(*it);

    sol[ctc].push_back(node);

}
void solve ( void )
{
    for(int i(1); i <= n ; ++i )

        if(!used[i])
            DFP(i);

    while(!S.empty())
    {
        if(!used_ctc[S.top()])
          {
           DFM(S.top());
           ++ctc;
          }
         S.pop();
    }

}

void write( void )
{
    vector<int>::iterator it;
    fprintf(g,"%d\n",ctc);
    for(int i(0); i < ctc; ++i )

     {
        for(it=sol[i].begin(); it != sol[i].end(); ++it )
            {
                fprintf(g,"%d ",*it);
            }
       fprintf(g,"\n");
    }
fclose(g);
}
int main( void )
{
    read();
    solve();
    write();
    return 0;
}