Cod sursa(job #3303473)

Utilizator robigiirimias robert robigi Data 15 iulie 2025 20:04:32
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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;
    if (nodes[x] == nullptr)
        nodes[x] = newNode;
    else
    {
        newNode->next = nodes[x];
        nodes[x] = newNode;
    }
}

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

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 = 0; i < sortedNodes.size(); ++i)
    {
        fout << sortedNodes[i] << " ";
    }

    return 0;
}