Cod sursa(job #3165518)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 6 noiembrie 2023 13:30:54
Problema Sortare topologica Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 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;

vector<int> graph[MAX_NODES + 1];

bitset<MAX_NODES + 1> fr;

int sortedNodes[MAX_NODES + 1][MAX_NODES + 1];
int sortedNodesLen;

void topologicalSort(int &sortedNodesLen, int sortedNodes[MAX_NODES + 1][MAX_NODES + 1], int startNode, int line) {
    for (vector<int>::iterator it = graph[startNode].begin(); it < graph[startNode].end(); ++it) {
        if (fr[*it] == 0) {
            sortedNodes[line][++sortedNodesLen] = *it;
            fr[*it] = 1;
            topologicalSort(sortedNodesLen, sortedNodes, *it, line);
        }
    }
}

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);
    }
    int line = 1;
    for (int i = 1; i <= noNodes; ++i) {
        if (graph[i].size() == 0) {
            sortedNodes[line][++sortedNodesLen] = i;
            fr[i] = 1;
        }
    }
    for (int i = 1; i <= noNodes; ++i) {
        if (fr[i] == 0) {
            ++line;
            sortedNodesLen = 0;
            sortedNodes[line][++sortedNodesLen] = i;
            fr[i] = 1;
            topologicalSort(sortedNodesLen, sortedNodes, i, line);
        }
    }
    for (int i = line; i >= 1; --i) {
        for (int j = 1; sortedNodes[i][j] != 0; ++j) {
            fout << sortedNodes[i][j] << ' ';
        }
    }
    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
 */