Cod sursa(job #2195477)

Utilizator stefantagaTaga Stefan stefantaga Data 16 aprilie 2018 15:22:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
struct nana
{
    int val,poz;
}fr[50001];
vector <int> v[50001];
int viz[50001];
int timp;
void df(int x)
{
    vector <int> :: iterator it;
    viz[x]=1;
    for (it=v[x].begin();it!=v[x].end();it++)
    {
        if (!viz[*it])
        {
            df(*it);
        }
    }
    timp++;
    fr[x].val=timp;
    fr[x].poz=x;
}
int compare (nana a,nana b)
{
    return (a.val>b.val)||(a.val==b.val&&a.poz<b.poz);
}
int n,m,i,x,y;
int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>x>>y;
        if (x!=y)
        {
            v[x].push_back(y);
        }
    }
    for (i=1;i<=n;i++)
    {
        if (viz[i]==0)
        {
            df(i);
        }
    }
    sort (fr+1,fr+n+1,compare);
    for (i=1;i<=n;i++)
    {
        g<<fr[i].poz<<" ";
    }
    return 0;
}