Cod sursa(job #916791)

Utilizator cont_testeCont Teste cont_teste Data 16 martie 2013 21:36:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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];

int 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);
    }
}
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;

}