Cod sursa(job #2757856)

Utilizator lahayonTester lahayon Data 6 iunie 2021 22:12:27
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 50000;


int main(){    
    
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");

 
    int N, M;
    cin >> N >> M;
    vector<int> graph[MAX_N];
    vector<int> degree(MAX_N, 0);
    int x, y;
    for(int i = 0; i < M; ++i){
        cin >> x >> y;
        --x; --y;
        ++degree[y];
        graph[x].push_back(y);
    }

    queue<int> Q;
    for(int i = 0; i < N; ++i)
        if(!degree[i]){
            Q.push(i);
            cout << i + 1 << " ";
        }
    while(!Q.empty()){

        for(int i = 0; i < graph[Q.front()].size(); ++i)
            if(--degree[graph[Q.front()][i]] == 0){
                Q.push(graph[Q.front()][i]);
                cout << graph[Q.front()][i] + 1 << " ";
            }
        Q.pop();
    }

   cin.close();
   cout.close();
  
  return 0;
	
}