Cod sursa(job #282511)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 17 martie 2009 19:48:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define N 50001

using namespace std;

struct list{int ind, info;} a[N];

int *A[N];
int post[N], viz[N], nr, n, m, i;

void dfs(int x)
{
             int i;
             viz[x] = 1;
             for(i = 1; i <= A[x][0]; i++)
                   if(!viz[A[x][i]])
                        dfs(A[x][i]);
             post[++nr] = x;
}

int main()
{
          freopen("sortaret.in","r", stdin);
          freopen("sortaret.out","w",stdout);
          
          int x, y, j;
          
          scanf("%d %d", &n, &m);
                    
          for(i = 1; i <= n; i++)
          {
                  A[i] = (int *)realloc(A[i], sizeof(int));
                  A[i][0] = 0;
          }
           
          for(i = 0; i < m; i++)
          {
                  scanf("%d %d", &x, &y);
                  A[x][0]++;
                  A[x] = (int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
                  A[x][A[x][0]] = y;
          }
          
          for(i = 1; i <= n; i++)
                if(viz[i] == 0)
                          dfs(i);
         
          for(i =n; i >= 1; i--)
                printf("%d ", post[i]);
          return 0;
}