Cod sursa(job #1339056)

Utilizator sulzandreiandrei sulzandrei Data 10 februarie 2015 17:23:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <algorithm>
using namespace std;
#include <list>
#include <vector>
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> v[50001];
    struct fo{
    int ind,t;} f[50001];
      bool c[50001];
int timp;
void qu(int st, int dr)
{
    int i,j,pivot;
    i = st;
    j = dr;
    pivot = f[(st+dr)/2].t;
    while(i<j)
    {
        while(f[i].t>pivot)
            i++;
        while(f[j].t<pivot)
            j--;
        if (i<=j)
        {
            struct fo x;
            x = f[i];
            f[i] = f[j];
            f[j] = x;
           i++; j--;
        }
    }
    if (i<dr)
        qu(i,dr);
    if (j>st)
        qu(st,j);
}
void ca(int u)
{
    c[u] = true;
    unsigned int j;
    for(j=0;j<v[u].size();j++)
        if(!c[v[u][j]])
            ca(v[u][j]);
    f[u].t = timp = timp+1;
}

int main()
{
    int n,m,i,x,y;
    in>>n>>m;
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        v[x-1].push_back(y-1);
    }
    for(i=0;i<n;i++)
    {
        f[i].t = 0;
        f[i].ind = i;
    }
    timp = 0;
    for(i=0;i<n;i++)
        if (!c[i])
           {
               ca(i);
               c[i] = true;
           }
    qu(0,n-1);
    for(i=0;i<n;i++)
        out<<f[i].ind+1<<" ";
}