Pagini recente » Cod sursa (job #3294995) | Cod sursa (job #1633292) | Cod sursa (job #2886531) | Cod sursa (job #3199987) | Cod sursa (job #695884)
Cod sursa(job #695884)
#include <cstdio>
int n, m;
int notr[50002];
int indx[50002];
struct Con {
unsigned short b, a;
} con[100002], depth[50002];
unsigned int * addr;
void qs(int l, int r) {
int i = l;
int j = r;
unsigned int p = addr[(i + j) / 2];
while (i <= j) {
while (addr[i] < p) {++i;}
while (addr[j] > p) {--j;}
if (i <= j) {
unsigned int t = addr[i];
addr[i] = addr[j];
addr[j] = t;
++i;
--j;
}
}
if (l < j) {qs(l, j);}
if (i < r) {qs(i, r);}
}
void ls() {
int k = 0;
for (int i = 0; i < m; ++i) {
if (k != con[i].a) {
k = con[i].a;
indx[k] = i;
}
}
}
void sign(int a, int d = 1) {
if (depth[a].a < d) {
depth[a].a = d;
for (int i = indx[a]; con[i].a == a; ++i) {
sign(con[i].b, d + 1);
}
}
}
int main() {
FILE * in = fopen("sortaret.in", "rt");
FILE * out = fopen("sortaret.out", "wt");
fscanf(in, "%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
fscanf(in, "%hu%hu", &con[i].a, &con[i].b);
notr[con[i].b] = 1;
}
addr = (unsigned int *)con;
qs(0, m - 1);
ls();
for (int i = 1; i <= n; ++i) {
depth[i].b = i;
if (!notr[i]) {
sign(i);
}
}
addr = (unsigned int *)depth;
qs(1, n);
for (int i = 1; i <= n; ++i) {
fprintf(out, "%d ", depth[i].b);
}
fclose(in);
fclose(out);
}