Cod sursa(job #2858717)

Utilizator CiuiGinjoveanu Dragos Ciui Data 28 februarie 2022 12:15:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 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];
int noParents[MAX_SIZE];
 
void topologicalSort(int peaks) { // nu sorteaza bine
    queue<int> positions;
    for (int i = 1; i <= peaks; ++i) {
        if (noParents[i] == 0) {
            positions.push(i);
            noParents[i] = 1;
        }
    }
    while (!positions.empty()) {
        int currentPeak = positions.front();
        positions.pop();
        for (int i = 0; i < graph[currentPeak].size(); ++i) {
            --noParents[graph[currentPeak][i]];
            if (noParents[graph[currentPeak][i]] == 0) {
                int nextPeak = graph[currentPeak][i];
                positions.push(nextPeak);
                noParents[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);
            ++noParents[end];
        }
    }
    topologicalSort(peaks);
    return 0;
}

 /*
  
  6 6
  6 3
  3 4
  4 2
  5 2
  5 1
  6 1 -> 5 6 2 1 3 4 gresit
  
  
  3 3
  1 2
  1 2
  2 3 -> 1 2 3 ok
  
  10 4
  4 2
  1 2
  3 2
  10 9 -> 1 3 4 5 6 7 8 10 2 9 ok
  
  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
    
  
  */