Cod sursa(job #3303481)

Utilizator robigiirimias robert robigi Data 15 iulie 2025 20:33:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

struct Node
{
    int node;
    Node *next;
    Node() : next(nullptr) {}
};

void insertNode(vector<Node *> &nodes, int x, int y)
{
    Node *newNode = new Node();
    newNode->node = y;
    newNode->next = nodes[x];
    nodes[x] = newNode;
}

void DFS(vector<Node *> &nodes, int x, vector<bool> &visited, vector<int> &sortedNodes)
{
    visited[x] = true;
    Node *current = nodes[x];
    while (current != nullptr)
    {
        if (!visited[current->node])
        {
            DFS(nodes, current->node, visited, sortedNodes);
        }
        current = current->next;
    }
    sortedNodes.push_back(x);
}

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

    int n, m;
    fin >> n >> m;

    vector<Node *> nodes(n + 1);
    vector<int> indegree(n + 1, 0);

    for (int i = 0; i < m; ++i)
    {
        int x, y;
        fin >> x >> y;

        insertNode(nodes, x, y);
        indegree[y]++;
    }

    vector<int> sortedNodes;
    vector<bool> visited(n + 1, false);

    for (int i = 1; i <= n; ++i)
    {
        if (indegree[i] == 0 && !visited[i])
        {
            DFS(nodes, i, visited, sortedNodes);
        }
    }

    for (int i = sortedNodes.size() - 1; i >= 0; --i)
    {
        fout << sortedNodes[i] << " ";
    }

    for (int i = 1; i <= n; ++i)
    {
        Node *current = nodes[i];
        while (current != nullptr)
        {
            Node *temp = current;
            current = current->next;
            delete temp;
        }
    }

    return 0;
}