Cod sursa(job #2664421)

Utilizator georgeblanarBlanar George georgeblanar Data 28 octombrie 2020 16:51:10
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>

using namespace std;

#define maxn 100010

ifstream f ("sortaret.in");
ofstream g ("sortaret.out");

int n, m;
vector<int> adj[maxn];
int ordering[maxn];
bool visited[maxn];


void dfs(int node, vector<int> &visitedList)
{
    visited[node] = true;

    for(auto next: adj[node])
    {
        if(!visited[next])
            dfs(next, visitedList);
    }
    visitedList.push_back(node);
}

void topsort()
{
    int i = n;

    for(int at = 1; at <= n; at++)
    {
        if(!visited[at])
        {
            vector<int> visitedNodes;

            dfs(at, visitedNodes);


            for(int nodeId: visitedNodes) {
                cout << nodeId << " ";
                ordering[i] = nodeId;
                i--;
            }
            cout << '\n';
        }
    }
}

int main()
{
    f >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int a, b;
        f >> a >> b;
        adj[a].push_back(b);
    }

    topsort();

    for(int i = 1; i <= n; i ++)
        g << ordering[i] << " ";
    return 0;
}