Cod sursa(job #2036555)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 10 octombrie 2017 20:01:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int main()
{
    int vertices,edges;
    fin>>vertices>>edges;
    vector<vector<int>> path(vertices+5);
    vector<int> in(vertices+5);
    queue<int> ans,q;
    int x,y;
    for(;edges;edges--)
    {
        fin>>x>>y;
        path[x].push_back(y);
        in[y]++;
    }
    while(ans.size()<vertices)
    {
        for(int i=1;i<=vertices;i++)
        {
            if(in[i]==0)
            {
                ans.push(i);
                q.push(i);
                in[i]=-1;
            }
        }

        while(!q.empty())
        {
            x=q.front();
            for(int i=0;i<path[x].size();i++)
            {
                in[path[x][i]]--;
            }
            q.pop();
        }
    }
    while(!ans.empty())
    {
        fout<<ans.front()<<' ';
        ans.pop();
    }
    return 0;
}