Cod sursa(job #1470462)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 11 august 2015 13:06:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <vector>
#define NMAX 50007
FILE *fin, *fout;
using namespace std;
int n, m, x, y, in[NMAX], qu[NMAX], dr, sze;
vector<int> adj[NMAX];
int main()
{
    fin = freopen("sortaret.in", "r", stdin);
    fout = freopen("sortaret.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; ++i)
    {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        in[y]++;
    }
    for(int i = 1; i<= n; ++i)
    {
        if(in[i] == 0)
        {
            dr++;
            qu[dr] = i;
        }
    }
    for(int i = 1; i<= dr; ++i)
    {
        sze = adj[qu[i]].size();
        for(int j = 0; j< sze; ++j)
        {
            in[adj[qu[i]][j]]--;
            if(in[adj[qu[i]][j]] == 0)
            {
                dr++;
                qu[dr] = adj[qu[i]][j];
            }
        }
    }
    for(int i = 1; i<= dr; ++i) printf("%d ", qu[i]);printf("\n");
    fclose(fin);
    fclose(fout);
    return 0;
}