Cod sursa(job #2572171)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 5 martie 2020 11:58:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;

const int NMAX=50005;

int pred[NMAX],sol[NMAX];
vector<int> succ[NMAX];
queue<int> q;

int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d", &x, &y);
        pred[y]++;
        succ[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        if(!pred[i])
            q.push(i);
    int cnt=0;
    while(!q.empty()){
        int top=q.front();
        for(int i=0;i<(int)succ[top].size();i++){
            pred[succ[top][i]]--;
            if(!pred[succ[top][i]])
                q.push(succ[top][i]);
        }
        sol[++cnt]=top;
        q.pop();
    }
    for(int i=1;i<=cnt;i++)
        printf("%d ", sol[i]);
    return 0;
}