Cod sursa(job #1567636)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 13 ianuarie 2016 17:10:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int dmax = 50000;
const int dim = 100000;

struct MUCHIE {int a, b;};
MUCHIE m[dim + 1];

int inc[dmax + 1];

int C[dmax + 1];
int d[dmax + 1];

int N, M;

bool exc(MUCHIE e1, MUCHIE e2)
{
    if(e1.a == e2.a) return e1.b < e2.b;
    else
        return e1.a < e2.a;
}

int main()
{
    int i, x, y, p, u;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y;

        d[y]++; //GRADUL INTERIOR AL NODULUI y

        m[i].a = x;
        m[i].b = y;
    }

    sort(m + 1, m + M + 1, exc);

    inc[ m[1].a ] = 1;

    for(i = 2; i <= M; i++)
        if(m[i].a != m[i-1].a) inc[ m[i].a ] = i;

    p = 1; u = 0;

    //INSEREZ IN COADA NODURILE i cu d[i] == 0
    for(i = 1; i <= N; i++)
        if(!d[i])
        {
            u++;
            C[u] = i;
        }

    while(p <= u)
    {
        x = C[p];

        //PARCURG VECINII LUI x
        for(i = inc[x]; m[i].a == x; i++)
        {
            //m[i].b

            d[ m[i].b ]--;

            if(!d[ m[i].b ])
            {
                u++;
                C[u] = m[i].b;
            }
        }

        p++;
    }

    for(i = 1; i <= N; i++) out << C[i] <<" ";

    return 0;
}