Cod sursa(job #2197831)

Utilizator sergiudnyTritean Sergiu sergiudny Data 22 aprilie 2018 22:21:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
#define DM 50005
#define pb push_back
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int>G[DM];
int ind[DM],p[DM],n,m,a,b,currInd;
pii srt[DM];

bool cmp(pii a,pii b){
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

void dfs(int nod){
    ind[nod]=++currInd;
    for(auto i:G[nod]) dfs(i);
}

int main()
{
    fin>>n>>m;
    while(m--){
        fin>>a>>b;
        G[a].pb(b);
        p[b]++;
    }
    for(int i=1;i<=n;++i) if(!p[i])
        dfs(i);
    for(int i=1;i<=n;++i) srt[i]={i,ind[i]};
    sort(srt+1,srt+n+1,cmp);
    for(int i=1;i<=n;++i) fout<<srt[i].x<<" ";

    return 0;
}