Cod sursa(job #2660381)

Utilizator DiagrDiana Grigore Diagr Data 19 octombrie 2020 09:37:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n,m;
vector<int> adj[50001];
queue<int> q;
int grade[50001];

void dfs()
{
   while(!q.empty())
   {
       int p = q.front();
       q.pop();
       for(auto x : adj[p])
       {
           grade[x]--;
           if(!grade[x])
               q.push(x);
       }
       g << p << " ";
   }
}

void sortareTopologica()
{
    for(int i = 1; i <= n; i++)
        if(grade[i] == 0)
            q.push(i);
    dfs();
}
int main() {
    f >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
        grade[y]++;             //pt fiecare muchie destinatie, cresc gradul
    }
    sortareTopologica();

    return 0;
}