Cod sursa(job #3257522)

Utilizator aeru1Ianos Alex-Marian aeru1 Data 18 noiembrie 2024 09:26:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

#define TITLE "sortaret"
ifstream f (TITLE".in");
ofstream g (TITLE".out");

bitset<50001>Visited;
stack<int> Answer;

void dfs(int Node, vector<vector<int>> &Graph)
{
    Visited[Node]=true;
    for(auto it : Graph[Node])
        if(!Visited[it])
        dfs(it,Graph);
    Answer.push(Node);
}

int main()
{
    int n,m;
    f>>n>>m;
    vector<vector<int>> Graph(n+1);
    for(int i=0; i<m; i++)
    {
        int a,b;
        f>>a>>b;
        Graph[a].emplace_back(b);
    }
    priority_queue<pair<int,int>> PQ;
    for(int i=1; i<=n; i++)
        PQ.push({-Graph[i].size(),i});
    for(; !PQ.empty(); PQ.pop())
        if(!Visited[PQ.top().second])
        dfs(PQ.top().second,Graph);
    for(;!Answer.empty(); Answer.pop())
        g<<Answer.top()<<' ';
    return 0;
}