Cod sursa(job #3224813)

Utilizator MagicantPlusIuoras Andrei MagicantPlus Data 16 aprilie 2024 11:53:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <forward_list>
#include <stack>

using namespace std;

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

void dfs(int start, vector<forward_list<int>> &adjacent, forward_list<int> &sorted, vector<bool> &visited);

int main()
{
    int n, m;
    forward_list<int> sorted;
    vector<forward_list<int>> adjacent;

    fin >> n >> m;
    adjacent.resize(n);
    
    for(int i = 0; i < n; i++)
    {
        int l, r;

        fin >> l >> r;
        l--;
        r--;

        adjacent[l].push_front(r);
    }

    vector<bool> visited(n, false);

    for(int node = 0; node < n; node++)
    {
        if(!visited[node])
        {
            dfs(node, adjacent, sorted, visited);
        }
    }

    for(auto &e : sorted)
    {
        fout << e + 1 << ' ';
    }

    return 0;
}

void dfs(int start, vector<forward_list<int>> &adjacent, forward_list<int> &sorted, vector<bool> &visited)
{
    stack<int> next;
    int node;
    bool br;

    next.push(start);
    visited[start] = true;

    while(!next.empty())
    {
        node = next.top();
        br = false;

        for(auto &neighbor : adjacent[node])
        {   
            if(!visited[neighbor])
            {
                visited[neighbor] = true;
                next.push(neighbor);
                br = true;
                break;
            }
        }

        if(br)
            continue;

        sorted.push_front(node);
        next.pop();
    }
}