Cod sursa(job #2394288)

Utilizator darisavuSavu Daria darisavu Data 1 aprilie 2019 15:12:35
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,t[50005],i,j,rad,x,y,m;
vector<int>v[50005];
queue<int>q;
struct punct
{
    int x,y;
}a[50005];
int compar(punct x,punct y)
{
    return (x.x<y.x||(x.x==y.x&&x.y<y.y));
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        t[y]=x;
        v[x].push_back(y);
    }
    for(i=1;i<=n;i++)
    {
        if(t[i]==0)
        {
            rad=i;
            break;
        }
    }
    a[rad].x=1;
    a[rad].y=rad;
    q.push(rad);
    int ad=1;
    while(!q.empty())
    {
        ad++;
        for(i=0;i<v[q.front()].size();i++)
        {
            if(a[v[q.front()][i]].x==0){a[v[q.front()][i]].x=ad;a[v[q.front()][i]].y=v[q.front()][i];}
            q.push(v[q.front()][i]);
        }
        q.pop();
    }
    sort(a+1,a+n+1,compar);
    for(i=1;i<=n;i++)
    {
        if(a[i].x==0) a[i].y=i;
        g<<a[i].y<<" ";
    }
    return 0;
}