Cod sursa(job #2576646)

Utilizator tudormoldovan1Tudor Moldovan tudormoldovan1 Data 6 martie 2020 21:23:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda imded Marime 0.89 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<vector<int>>G;
vector<int>L;
int n,m,In[50005];
int ind, I[50005];
void Citire()
{
    fin>>n>>m;
    G.resize(n+1);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
        In[y]++;
    }
}
void TopSort()
{
    queue<int>Q;
    for(int i=1;i<=n;i++)
        if(In[i]==0)
            Q.push(i);
    while(!Q.empty())
    {
        int x=Q.front();
        L.push_back(x);
        I[x]=++ind;
        Q.pop();
        for(auto y : G[x])
        {
            In[y]--;
            if(In[y]==0)
                Q.push(y);
        }
    }
}
void Afisare()
{
    for(auto x : L)
        fout<<x<<" ";
}
int main()
{
    Citire();
    TopSort();
    Afisare();
    return 0;
}