Cod sursa(job #3169219)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 14 noiembrie 2023 13:40:26
Problema Sortare topologica Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

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

const int MAX_NODES = 20000;

int sortedNodes[MAX_NODES + 1];
int sortedNodesLen;

vector<int> graph[MAX_NODES + 1];

int main() {
    int noNodes, noEdges;
    fin >> noNodes >> noEdges;
    for (int i = 1; i <= noEdges; ++i) {
        int start, end;
        fin >> start >> end;
        graph[start].push_back(end);
    }
    bool allNodesFound = 0;
    bitset<MAX_NODES + 1> fr = {0};
    while (allNodesFound == 0) {
        allNodesFound = 1;
        for (int i = 1; i <= noNodes; ++i) {
            for (vector<int>::iterator it = graph[i].begin(); it < graph[i].end(); ++it) {
                if (graph[*it].size() == 0) {
                    allNodesFound = 0;
                    if (fr[*it] == 0) {
                        sortedNodes[++sortedNodesLen] = *it;
                    }
                    fr[*it] = 1;
                    graph[i].erase(graph[i].begin() + (it - graph[i].begin()));
                    --it;
                }
            }
        }
    }
    for (int i = 1; i <= noNodes; ++i) {
        if (fr[i] == 0) {
            sortedNodes[++sortedNodesLen] = i;
        }
    }
    for (int i = sortedNodesLen; i >= 1; --i) {
        fout << sortedNodes[i] << ' ';
    }
    return 0;
}
/*
 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
 
 4 3
 1 2
 3 2
 4 1
 =>
 4 3 1 2
 */