Cod sursa(job #2670534)

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

using namespace std;

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

int n , m , interior[NMAX];

queue <int> Q;

vector <int> muchii[NMAX];

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

int main()
{
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i ++)
    {
        int x , y;
        fin >> x >> y;
        arc[make_pair(x , y)] ++;
        if(arc[make_pair(x , y)] == 1)
        {
            muchii[x].push_back(y);
            interior[y] ++;
        }
    }
    for(int i = 1 ; i <= n ; i ++)
        if(!interior[i])
            Q.push(i);
    while(!Q.empty())
    {
        int curent = Q.front();
        Q.pop();
        for(int i = 0 ; i < muchii[curent].size() ; i ++)
        {
            interior[muchii[curent][i]] --;
            if(!interior[muchii[curent][i]])
                Q.push(muchii[curent][i]);
        }
        fout << curent << ' ';
    }
    return 0;
}