Cod sursa(job #1908952)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 7 martie 2017 11:07:44
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
struct pereche
{
    int niv, nodd;
};
bool sortare(pereche a, pereche b)
{
    if(a.niv <= b.niv) return true;
    return false;
}
pereche info[50001];
char marcat[50001];
vector <int> muchie[50001];
stack <int> stiva;
FILE *fin = fopen("sortaret.in", "r");
FILE *fout= fopen("sortaret.out", "w");
int main()
{
    int n,m;
    fscanf(fin, "%d%d", &n ,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fscanf(fin, "%d%d", &x, &y);
        muchie[x].push_back(y);
        marcat[y]=1;
    }
    for(int i=1;i<=n;i++)
    {
        info[i].nodd=i;
        if(marcat[i]==0)
        {
            stiva.push(i);
            while(!stiva.empty())
            {
                int nod = stiva.top();
                stiva.pop();
                for(auto node : muchie[nod])
                {
                    if(info[node].niv < info[nod].niv + 1) info[node].niv = info[nod].niv + 1;
                    stiva.push(node);
                }
            }
        }
    }
    sort(info+1,info+n+1,sortare);
    for(int i=1;i<=n;i++)
    {
        fprintf(fout, "%d ", info[i].nodd);
    }
    return 0;
}