Cod sursa(job #1489666)

Utilizator serbanSlincu Serban serban Data 21 septembrie 2015 20:25:35
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

pair<int, int> v[100005];
int rez[50005];
int s[50005];
bool pus[50005];

int main()
{
    FILE *f = fopen("sortaret.in", "r");
    FILE *g = fopen("sortaret.out", "w");

    int n, m, x, y;
    fscanf(f, "%d %d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        fscanf(f, "%d %d", &x, &y);
        v[i].first = x;
        v[i].second = y;
        s[y] ++;
    }

    int k = 1;
    while(k <= n) {
        int mn = 50005;
        int poz;
        for(int i = 1; i <= n; i ++) {
            if(s[i] < mn && !pus[i]) {
                mn = s[i];
                poz = i;
            }
        }
        pus[poz] = true;
        rez[k] = poz;
        for(int i = 1; i <= m; i ++) {
            if(v[i].first == poz)
                s[v[i].second] --;
        }
        k ++;
    }
    for(int i = 1; i <= n; i ++)
        fprintf(g, "%d ", rez[i]);
    fprintf(g, "\n");
    return 0;
}