Cod sursa(job #921080)

Utilizator superman_01Avramescu Cristian superman_01 Data 20 martie 2013 19:19:39
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<cstdio>
#include<vector>

#define MAX_SIZE 50005

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

using namespace std;

vector <int> G[MAX_SIZE];
vector <int> order[MAX_SIZE];

bool used[MAX_SIZE];
int n,m;

void read( void )
{
    fscanf(f,"%d%d",&n,&m);
    int x,y;
    for(int i(1); i <= m; ++i )
    {
            fscanf(f,"%d%d",&x,&y);
            G[x].push_back(y);
    }
    fclose(f);
}
void DF(int node )
{
    vector <int> ::iterator it;
   used[node]=1;
   for(it=G[node].begin();it!=G[node].end(); ++it)
    if(!used[*it])
     DF(*it);
   order[0].push_back(node);

}

void solve ( void )
{

   for(int i(1); i <= n ; ++i )
       if(!used[i])
          DF(i);
}
void write( void )
{vector <int> ::iterator it;
    for(it=order[0].end()-1;it!=order[0].begin();--it)
        fprintf(g,"%d",*it);
    fprintf(g,"%d",*it);
    fclose(g);


}

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

}