Cod sursa(job #450019)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 7 mai 2010 16:11:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;
const int N_MAX = 50002;
int t;
int N,M;
vector <int> v[N_MAX];
int viz[N_MAX];
int top_sorted[N_MAX];
int dfs(int s)
{
    viz[s] = 1;
    for(int i = 0; i < v[s].size(); i++)
     if (!viz[v[s][i]])
      dfs(v[s][i]);
    top_sorted[++top_sorted[0]] = s;
}
int main()
{
        freopen("sortaret.in","r",stdin);
        freopen("sortaret.out","w",stdout);

        scanf("%d %d",&N,&M);

        for(int i = 1; i <= M; i++)
        {
                int x,y;
                scanf("%d %d",&x,&y);
                v[x].push_back(y);
        }

        for(int i = 1; i <= N; i++)
         if (!viz[i])
          {
              dfs(i);
          }
        for(int i = top_sorted[0]; i >= 1; i--)
         printf("%d ",top_sorted[i]);
        printf("\n");




        return 0;



}