Cod sursa(job #3163683)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 31 octombrie 2023 21:09:50
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAX_LENGTH = 50000;

int pos(int noNodes, int nodes[MAX_LENGTH + 1], int number) {
    int left = 1, right = noNodes;
    while (left < right) {
        int middle = (left + right) / 2;
        if (nodes[middle] < number) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }
    return left;
}

int main() {
    int noNodes, noEdges;
    fin >> noNodes >> noEdges;
    int nodes[MAX_LENGTH + 1];
    for (int i = 1; i <= noNodes; ++i) {
        nodes[i] = i;
    }
    for (int i = 1; i <= noEdges; ++i) {
        int start, end;
        fin >> start >> end;
        int startPos = pos(noNodes, nodes, start), endPos = pos(noNodes, nodes, end);
        if (startPos > endPos) {
            nodes[startPos] = end;
            nodes[endPos] = start;
        }
    }
    for (int i = 1; i <= noNodes; ++i) {
        fout << nodes[i] << ' ';
    }
    return 0;
}