Cod sursa(job #2651763)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 23 septembrie 2020 15:39:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

int *A[100005];
int postord[100005];
int vizi[100005];
int nr =0;

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[++nr]=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=1;i<=nr;i++)
    {
        out<<postord[i]<<" ";
    }
    return 0;
}