Cod sursa(job #2651708)

Utilizator racleta31Andreican Rares racleta31 Data 23 septembrie 2020 13:01:01
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int *A[50005];
vector <int> postord;
int vizi[50005];
void DFS(int x)
{
    vizi[x]=1;
    for(int i=1;i<=A[x][0];i++)
    {
        if(!vizi[A[x][i]])
        {
            DFS(A[x][i]);
        }
    }
    postord.push_back(x);
}
int main()
{
    int n, m;
      in>>n>>m;
    for(int i=1;i<=n;i++)
    {
        A[i]=(int *)realloc(A[i],sizeof(int));
        A[i][0]=0;
    }


    for(int i=1;i<=n;i++)
    {
        int a, b;
        in>>a>>b;
        A[a][0]++;
        A[a]=(int *)realloc (A[a], (A[a][0]+1)*sizeof(int));
        A[a][A[a][0]]=b;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vizi[i])
        {
            DFS(i);
        }
    }
    for(int i=n-1;i>=0;i--)
    {
        out<<postord[i]<<" ";
    }
    return 0;
}