Cod sursa(job #2724042)

Utilizator Kovacs_MarkKovacs Mark Daniel Kovacs_Mark Data 16 martie 2021 11:51:52
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
#define N 100001
#define M 400001
struct {int x,y;} u[M];
int p[N],c[N],v[N],n,m,k,a,b;
int main()
{
    int i,j,k,x,y;
    //citire
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u[i].x>>u[i].y;
        v[u[i].y]++;
    }
    //sortare muchii
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(u[i].x>u[j].x)
                swap(u[i],u[j]);
    //indexare
    for(i=1;i<=n;i++)
        if(u[i].x!=u[i-1].x)
            p[u[i].x]=i;
    //sortare topologica
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
            if(v[i]==0)
            {
                fout<<i<<' ';
                v[i]=-1;
                for(j=p[i];u[j].x==i;j++)
                    v[u[j].y]--;
                break;
            }
    }
    return 0;
}