Cod sursa(job #2922115)

Utilizator Paul_DobrescuPaul Dobrescu Paul_Dobrescu Data 4 septembrie 2022 10:33:22
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

int main()
{
// #ifndef ONLINE_JUDGE
// 	freopen("input", "r", stdin);
// 	freopen("output", "w", stdout);
// #endif
    int n, m;
    reader >> n >> m;
	vector <vector <int>> graf(n + 1, vector <int> ());
    vector <int> grade(n + 1, 0);
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        reader >> x >> y;
        graf[x].emplace_back(y);
        grade[y]++;
    }
    queue <int> q;
    for(int i = 1; i <= n; ++i)
    {
        if(grade[i] == 0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int r = q.front();
        q.pop();
        writer << r << " ";
        for(auto it : graf[r])
        {
            grade[it]--;
            if(grade[it] == 0)
                q.push(it);
        }
    }
	return 0;
}