Cod sursa(job #3275643)

Utilizator sheesh07Andrei Giurgiu sheesh07 Data 11 februarie 2025 12:44:58
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>

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

int n, m, c[101], k, x, y, start[101], t[2][101], fr[101], man, st=1, dr=0;

void liste(int i, int j)
{
    k++;
    t[0][k]=j;
    t[1][k]=start[i];
    start[i]=k;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        liste(x, y);
        fr[y]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(fr[i]==0)
        {
            cout<<i<<' ';
            man=start[i];
            while(man)
            {
                c[++dr]=t[0][man];
                man=t[1][man];
            }
        }
    }
    for(int i=st;i<=dr;i++)
    {
        fr[c[i]]--;
    }
    while(st<=dr)
    {
        x=c[st];
        if(fr[x]==0)
        {
            cout<<x<<' ';
            fr[x]=-1;
            man=start[x];
            while(man)
            {
                if(fr[t[0][man]]!=0)
                {
                    c[++dr]=t[0][man];
                    fr[t[0][man]]--;
                }
                man=t[1][man];
            }
        }
        else c[++dr]=x;
        st++;
    }
    return 0;
}