Cod sursa(job #1489679)

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

using namespace std;

vector<int> v[50005];
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[x].push_back(y);
    }
    for(int i = 1; i <= n; i ++)
        s[i] = v[i].size();

    int k = n;
    while(k) {
        int mn = 50005, poz;
        for(int i = 1; i <= n; i ++) {
            if(s[i] < mn && !pus[i]) {
                mn = s[i];
                poz = i;
            }
        }
        pus[poz] = true;
        for(int i = 1; i <= n; i ++) {
            if(!pus[i])
                for(int j = 0; j < v[i].size(); j ++) {
                    if(v[i][j] == poz)
                        s[i] --, j = v[i].size();
                }
        }
        rez[k] = poz;
        k --;
    }

    for(int i = 1; i <= n; i ++)
        fprintf(g, "%d ", rez[i]);
    fprintf(g, "\n");
    return 0;
}