Cod sursa(job #2422839)

Utilizator melutMelut Zaid melut Data 20 mai 2019 06:46:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>

using namespace std;


typedef unsigned short ushort;


string const inFile = "sortaret.in";
string const outFile = "sortaret.out";

ushort const MAX_N = 50 * 1000;


FILE *Read = fopen(inFile.c_str(), "r");
FILE *Write = fopen(outFile.c_str(), "w");


void CloseFiles(FILE *Read, FILE *Write) {
    fclose(Read);
    fclose(Write);
}


void ReadArcs(vector<vector<ushort>> &nodes) {
    ushort n;
    unsigned m;

    fscanf(Read, "%hu", &n);
    fscanf(Read, "%u", &m);

    nodes.resize(n);

    ushort node1;
    ushort node2;

    while (m--) {
        fscanf(Read, "%hu %hu", &node1, &node2);

        nodes[node2 - 1].push_back(node1 - 1);
    }
}


inline void DFS(
    vector<vector<ushort>> const &nodes,
    bitset<MAX_N> &visited,
    ushort const node)
{
    visited.set(node);

    for (unsigned i = 0; i < nodes[node].size(); ++i) {
        if (visited[nodes[node][i]] == true) {
            continue;
        }

        DFS(nodes, visited, nodes[node][i]);
    }

    fprintf(Write, "%hu ", node + 1);
}


int main() {
    vector<vector<ushort>> nodes;
    bitset<MAX_N> visited;

    ReadArcs(nodes);

    for (int i = nodes.size() - 1; i > 0; --i) {
        if (visited[i] == true) {
            continue;
        }

        DFS(nodes, visited, i);
    }

    CloseFiles(Read, Write);

    return 0;
}