Cod sursa(job #1231652)

Utilizator andreey_047Andrei Maxim andreey_047 Data 21 septembrie 2014 11:57:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#define in "sortaret.in","r",stdin
#define out "sortaret.out","w",stdout
#define nmax 50009
using namespace std;
int n,m,nr[nmax],Q[nmax];
vector<int>G[nmax];
inline void Sort(){
 int i,j;
 for(i=1;i<=n;i++)
    if(!nr[i]) Q[++Q[0]]=i;

  for(i=1;i<=n;i++){
    for(j = 0; j < G[Q[i]].size();j++){
        nr[G[Q[i]][j]]--;
        if(!nr[G[Q[i]][j]]) Q[++Q[0]]=G[Q[i]][j];
    }
  }
}
int main(){
    int i,x,y;
 freopen(in);
 freopen(out);
 scanf("%d%d",&n,&m);
  while(m--){
    scanf("%d%d",&x,&y);
    G[x].push_back(y);
    nr[y]++;
  }
  Sort();
    for(i=1;i<=n;i++)
        cout << Q[i]<<' ';
}