Cod sursa(job #2884702)

Utilizator CristianPavelCristian Pavel CristianPavel Data 4 aprilie 2022 17:50:30
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <stack>
using namespace std;

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

#define maxN 50001

typedef struct nod{
    int info;
    nod *leg;
} *pnod;

nod *List[maxN];
nod *p;

int N, M;
bool Visited[maxN];

stack <int> Stack;

void Add(int x, int y)
{  
    p = new nod;
    p -> info = y;
    p -> leg = List[x];
    List[x] = p;
}

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

void DFS(int i)
{
    nod *q = List[i];
    while(q != NULL)
    {
        if(Visited[q -> info] == false)
            Visited[q -> info] = true, DFS(q -> info);
        q = q -> leg;
    }
    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;
}