Cod sursa(job #3264583)

Utilizator Horia123144Musat Horia Gabriel Horia123144 Data 22 decembrie 2024 16:49:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
#define nmax 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
int cate_intra[nmax],sol[nmax],ind;
vector<int>L[nmax];
queue<int>q;
void sortare_topologica()
{
    while(!q.empty())
    {
        sol[++ind]=q.front();
        int x=q.front();
        for(auto i:L[x])
        {
            cate_intra[i]--;
            if(cate_intra[i]==0)
                q.push(i);
        }
        q.pop();
    }
}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x,y;
        fin>>x>>y;
        L[x].push_back(y);
        cate_intra[y]++;
    }
    for(int i=1;i<=n;i++)
        if(cate_intra[i]==0)
            q.push(i);
    sortare_topologica();
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<' ';
    return 0;
}