Cod sursa(job #2858554)

Utilizator CiuiGinjoveanu Dragos Ciui Data 27 februarie 2022 20:45:07
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
 
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
 
const int MAX_SIZE = 50005;
const int MAX_SUM = 1000000001;
 
vector<int> graph[MAX_SIZE];
bool hasParents[MAX_SIZE];
//int costs[MAX_SIZE][MAX_SIZE];
int distances[MAX_SIZE];
 
void findMinimumCosts(int peaks) {
    queue<int> positions;
    for (int i = 1; i <= peaks; ++i) {
        if (hasParents[i] == false) {
            positions.push(i);
            distances[i] = 1;
        }
    }
    while (!positions.empty()) {
        int currentPeak = positions.front();
        positions.pop();
        for (int i = 0; i < graph[currentPeak].size(); ++i) {
            if (distances[graph[currentPeak][i]] == 0) {
                positions.push(graph[currentPeak][i]);
                distances[graph[currentPeak][i]] = 1;
            }
        }
        fout << currentPeak << " ";
    }
}

int main() {
    int peaks, arches;
    fin >> peaks >> arches;
    for (int i = 1; i <= arches; ++i) {
        int start, end;
        fin >> start >> end;
        graph[start].push_back(end);
        hasParents[end] = true;
    }
    findMinimumCosts(peaks);
    return 0;
}
 /*
  
  un nod apare de mai multe ori?
  
  3 1
  1 3 ->
  
  5 2
  1 2
  2 4 ->
    
  
  */