Mai intai trebuie sa te autentifici.

Cod sursa(job #2530743)

Utilizator CriviCriveanu Bogdan Crivi Data 25 ianuarie 2020 11:26:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in;
ofstream out;

vector<set<int>> edge;

int n,m,visited[50005];

stack<int> sorted;

void DFS(int st)
{
    visited[st]=1;
    for(auto& it:edge[st])
    {
        if(!visited[it])
            DFS(it);
    }
    sorted.push(st);
}

void top_sort()
{
    for(int i=1;i<=n;i++)
        if(!visited[i])
            DFS(i);
}
int main()
{
    in.open("sortaret.in");
    out.open("sortaret.out");
    
    in>>n>>m;
    edge.resize(n+2);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        in>>x>>y;
        edge[x].insert(y);
    }
    top_sort();
    while (!sorted.empty()) {
        out<<sorted.top()<<" ";
        sorted.pop();
    }
    return 0;
}