Cod sursa(job #1194150)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 2 iunie 2014 22:53:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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;
}