Cod sursa(job #1189340)

Utilizator costyrazvyTudor Costin Razvan costyrazvy Data 22 mai 2014 15:05:24
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100005

vector < int > L[NMAX];
int P[NMAX],T[NMAX];
bool sel[NMAX];
int N,M,i,x,Lg;

bool cmp(int x,int y)
{
    return T[x]<T[y];
}

void DF(int nod)
{
    sel[nod]=true;

    for ( vector < int > :: iterator it=L[nod].begin();it!=L[nod].end();++it)
       {
           if (sel[*it]) continue;
           DF(*it);
       }

    T[nod]=++Lg;
    P[nod]=nod;
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

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

    for (i=1;i<=M;++i)
          L[scanf("%d",&x)].push_back(scanf("%d",&x));

    for (i=1;i<=N;++i)
      {
          if (sel[i]) continue;
          DF(i);
      }

    sort(P+1,P+N+1,cmp);

    for (i=1;i<=N;++i) printf("%d ",P[i]);
    printf("\n");

    return 0;
}