Cod sursa(job #2405497)

Utilizator eduardcadarCadar Eduard eduardcadar Data 14 aprilie 2019 16:15:57
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
#define dim 8192
int pz;
char ax[dim];
void cit(int &x) {
    x = 0;
    while (ax[pz] < '0' || ax[pz] > '9')
        if (++pz == dim) f.read(ax,dim), pz = 0;
    while (ax[pz] >= '0' && ax[pz] <= '9') {
        x = x * 10 + ax[pz] - '0';
        if (++pz == dim) f.read(ax,dim), pz = 0;
    }
}
int n, m, t[50001], a[100001], b[100001];
bool u[50001];
int find(int i) {
    if (t[i] != i) t[i] = find(t[i]);
    return t[i];
}
void uneste(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return;
    t[i] = j;
}
void afis(int i) {
    if (u[i]) return;
    if (t[i] == i) {g << i << ' '; u[i] = 1; return;}
    if (u[t[i]]) {g << i << ' '; u[i] = 1; return;}
    afis(t[i]);
    g << i << ' ';
    u[i] = 1;
}
int main()
{
    cit(n), cit(m);
    for (int i = 1; i <= m; ++i) cit(a[i]), cit(b[i]);
    for (int i = 1; i <= n; ++i) t[i] = i;
    for (int i = 1; i <= m; ++i) {
        if (a[i] > t[b[i]]) t[b[i]] = find(a[i]);
    }
    for (int i = 1; i <= n; ++i) afis(i);
    return 0;
}