Cod sursa(job #436174)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 8 aprilie 2010 10:27:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
# include <cstdio>
# include <vector>

using namespace std;

# define FIN "sortaret.in"
# define FOUT "sortaret.out"
# define MAX_N 50005

int s[MAX_N];
int fin[MAX_N];
int N, M, i, x, y, ct;
vector <int> G[MAX_N];

       void df(int nod) {
           s[nod] = 1;
           for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++it)
              if (!s[*it]) df(*it);
           
           fin[++ct] = nod;
       }

       int main() {
           freopen(FIN, "r", stdin);
           freopen(FOUT, "w", stdout);
           
           scanf("%d%d", &N, &M);
           for (i = 1; i <= M; ++i) {
               scanf("%d%d", &x, &y);
               
               G[x].push_back(y);;
           }
           
           for (i = 1; i <= N; ++i)
              if (!s[i]) df(i);
           
           for (i = ct; i >= 1; --i) printf("%d ", fin[i]);
           
           return 0;
       }