Cod sursa(job #2884631)

Utilizator CristianPavelCristian Pavel CristianPavel Data 4 aprilie 2022 14:09:07
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <stack>
#define maxN 50001
using namespace std;

ifstream cin ("sortaret.in");
ofstream cout ("sortaret.out");

int Matrix[maxN][maxN], N, M;
bool Visited[maxN];
stack <int> Stack;

void Read()
{
    cin >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        int x, y;
        cin >> x >> y;
        Matrix[x][y] = 1;
    }
    for(int i = 1; i <= N; ++i)
        Visited[i] = false;
}

void DFS(int i)
{
    for(int j = 1; j <= N; ++j)
        if(Matrix[i][j] == 1 && Visited[j] == false)
            Visited[j] = true, DFS(j);
    Stack.push(i);
}

void Top_sort()
{
    for(int i = 1; i <= N; ++i)
        if(Visited[i] == false) Visited[i] = true, DFS(i);
}

void Print()
{
    while(!Stack.empty())
    {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}
int main()
{
    Read();
    Top_sort();
    Print();
    return 0;
}