Cod sursa(job #2858556)

Utilizator CiuiGinjoveanu Dragos Ciui Data 27 februarie 2022 20:59:45
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 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;
 
vector<int> graph[MAX_SIZE];
bool hasParents[MAX_SIZE];
int goneThrough[MAX_SIZE];
 
void findMinimumCosts(int peaks) {
    queue<int> positions;
    for (int i = 1; i <= peaks; ++i) {
        if (hasParents[i] == false) {
            positions.push(i);
            goneThrough[i] = 1;
        }
    }
    while (!positions.empty()) {
        int currentPeak = positions.front();
        positions.pop();
        for (int i = 0; i < graph[currentPeak].size(); ++i) {
            if (goneThrough[graph[currentPeak][i]] == 0) {
                int nextPeak = graph[currentPeak][i];
                positions.push(nextPeak);
                goneThrough[nextPeak] = 1;
            }
        }
        fout << currentPeak << " ";
    }
}

int main() {
    int peaks, arches;
    fin >> peaks >> arches;
    for (int i = 1; i <= arches; ++i) {
        int start, end;
        fin >> start >> end;
        if (start != end) {
            graph[start].push_back(end);
            hasParents[end] = true;
        }
    }
    findMinimumCosts(peaks);
    return 0;
}

 /*
  
  50000 1
  499 498 -> ok (498 e dupa 499)
  
  6 7
  1 2
  1 4
  4 3
  3 5
  2 3
  1 3
  4 3 -> 1 6 2 4 3 5 ok
  
  10 1
  10 9 -> 1 2 3 4 5 6 7 8 10 9 ok
  
  9 8
  1 2
  1 3
  3 4
  3 5
  5 9
  4 6
  4 7
  4 8 -> 1 2 3 4 5 6 7 8 9 ok
  
  15 14
  14 9
  14 1
  14 2
  14 3
  3 4
  10 14
  2 8
  1 7
  1 6
  15 10
  13 5
  11 12
  11 13
  10 11 -> 15 10 14 11 9 1 2 3 12 13 7 6 8 4 5 OK
  
  2 2
  1 2
  1 2 -> 1 2 ok
  
  7 1
  7 1 -> 2 3 4 5 6 7 1 ok
  
  6 4
  1 2
  2 3
  2 4
  5 6 -> 1 5 2 6 3 4 ok
  
  7 3
  1 2
  3 4
  5 6 -> 1 3 5 7 2 4 6 ok
    
  
  */