Cod sursa(job #1041843)

Utilizator mikeshadowIon Complot mikeshadow Data 26 noiembrie 2013 11:27:17
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <string.h>

#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)

#define INF 1000001

using namespace std;


#ifndef TEST
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif

#define MAXN 50000

struct ed
{
    int x,y;
};

int n,m;

int a[MAXN];

vector<int> L,S;

vector<ed> es;

int main()
{
    fin>>n>>m;

    memset(a,0,sizeof(a));

    for (int i=0; i<m; i++)
    {
        ed e;
        fin>>e.x>>e.y;
        e.x--;
        e.y--;
        a[e.y]++;
        es.push_back(e);
    }

    for (int i=0; i<n; i++)
        if (a[i]==0)
            S.push_back(i);

    while (!S.empty())
    {
        int x;
        x = S.front();
        S.erase(S.begin());
        L.push_back(x);
        for (int i=0; i<es.size(); i++)
            if (es[i].x== x)
        {
            a[es[i].y]--;
            if (a[es[i].y]==0) S.push_back(es[i].y);
            es.erase(es.begin()+i);
            i--;
        }
    }

    for (int i=0; i<n; i++)
        fout<<L[i]+1<<' ';

    return 0;
}