Cod sursa(job #1193868)

Utilizator ZenusTudor Costin Razvan Zenus Data 2 iunie 2014 07:39:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100005

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

bool cmp(int x,int y)
{
    return Father[x]>Father[y];
}

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

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

    Father[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)
      {
          scanf("%d",&x);
          scanf("%d",&y);
          L[x].push_back(y);
      }

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