Cod sursa(job #2334691)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 2 februarie 2019 21:36:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax=50005;
const int INF=1000000000;

vector <int> g[nmax];
vector <int> rasp;

int deg[nmax];

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);
        g[x].push_back(y);
        deg[y]++;
    }
    int nr=0;
    while(nr<n)
    {
        for(int i=1;i<=n;i++)
        {
            if(deg[i]==0)
            {
                deg[i]=-INF;
                rasp.push_back(i);
                nr++;
                for(int j=0;j<g[i].size();j++)
                    deg[g[i][j]]--;
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ", rasp[i-1]);
    printf("\n");

    return 0;
}