Cod sursa(job #2670539)

Utilizator tudosa.bogdanTudosa Eduard-Bogdan tudosa.bogdan Data 10 noiembrie 2020 09:48:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define NMAX 50005

using namespace std;

FILE *fin = fopen("sortaret.in", "r");
FILE *fout = fopen("sortaret.out", "w");

int n, m, interior[NMAX];

int Q[NMAX];

vector <int> muchii[NMAX];
vector <int> ::iterator it;

map <pair <int, int>, int > arc;

int main()
{
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 1 ; i <= m ; i ++)
    {
        int x, y;
        fscanf(fin, "%d%d", &x, &y);
        muchii[x].push_back(y);
        interior[y] ++;
    }
    for(int i = 1 ; i <= n ; i ++)
        if(!interior[i])
            Q[++Q[0]] = i;;
    for(int i = 1 ; i <= n ; i ++)
    {
        int curent = Q[i];
        for(it = muchii[curent].begin() ; it != muchii[curent].end() ; it ++)
        {
            interior[*it] --;
            if(!interior[*it])
                Q[++ Q[0]] = *it;
        }
        fprintf(fout, "%d ", curent);
    }
    return 0;
}