Cod sursa(job #3163694)

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

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

const int MAX_NODES = 50000;
const int MAX_EDGES = 100000;

void pos(int noNodes, int nodes[MAX_NODES + 1], int start, int end, int &startPos, int &endPos) {
    for (int i = 1; i <= noNodes; ++i) {
        if (nodes[i] == start) {
            startPos = i;
        } else if (nodes[i] == end) {
            endPos = i;
        }
    }
}

int main() {
    int noNodes, noEdges;
    fin >> noNodes >> noEdges;
    int nodes[MAX_NODES + 1];
    for (int i = 1; i <= noNodes; ++i) {
        nodes[i] = i;
    }
    pair<int, int> edges[MAX_EDGES + 1];
    for (int i = 1; i <= noEdges; ++i) {
        fin >> edges[i].first >> edges[i].second;
    }
    bool isSorted = 0;
    while (isSorted == 0) {
        isSorted = 1;
        for (int i = 1; i <= noEdges; ++i) {
            int startPos = 0, endPos = 0;
            pos(noNodes, nodes, edges[i].first, edges[i].second, startPos, endPos);
            if (startPos > endPos) {
                isSorted = 0;
                swap(nodes[startPos], nodes[endPos]);
            }
        }
    }
    for (int i = 1; i <= noNodes; ++i) {
        fout << nodes[i] << ' ';
    }
    return 0;
}