This program takes WA. It's simple, O(N), no pointers... But WA!!!


/*
 *  ACM Online
 *  The Prufer Code - Problem 1069
 *
 */

#include <stdio.h>
#include <stdlib.h>

#define NODS 7510

int n, how[NODS], flag[NODS], sum[NODS], sol[NODS], s[NODS];


int main()
{
    int i, j, k, next;

    n = 0;
    while (1)
    {
        scanf("%d", &s[n++]);
        if (!s[n - 1]) break;
        flag[--s[n - 1]]++;
    }
    for (i = 0; i < n; i++)
        how[i] = flag[i] + 1;
    for (i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + how[i - 1], how[i - 1] = 0;

    for (i = 0; i < n; i++)
        if (!flag[i])
            next = i, i = n;
    for (i = 0; i < n - 1; i++)
    {
        k = s[i];
        sol[sum[k] + how[k]++] = next; sol[sum[next] + how
[next]++] = k;
        flag[k]--; flag[next]--;
        while (flag[++next]);
        if (k < next && !flag[k]) next = k;
    }
    /*  sort&#8224;m fii  */
    for (i = 0; i < n; i++)
        for (k = sum[i]; k < sum[i] + how[i]; k++)
            for (j = k + 1; j < sum[i] + how[i]; j++)
                if (sol[k] > sol[j])
                    next = sol[k], sol[k] = sol
[j], sol[j] = next;

    for (i = 0; i < n; i++)
    {
        printf("%d:", i + 1);
        for (k = sum[i]; k < sum[i] + how[i]; k++)
            printf(" %d", sol[k] + 1);
        printf("\n");
    }
    return 0;
}

You see, IMHO there's no O(N) algo solving this problem. If I'm not
mistaken, my algo was O(N*logN), anyway I used heaps.

I found an algorithm that turns a Prufer code into edges with O(N)
time. This problem asks you to construct also the tree which I've
done without pointers or heaps... Am I wrong?
Please send my your AC source (ste_fanus@k.ro) or please send me a
test which my source doesn't pass. Thanks!

/*
 *  ACM Online
 *  The Pruffer Code - Problem 1069
 */

#include <stdio.h>
#include <stdlib.h>

#define NODS 16000

long n, how[NODS], flag[NODS], sum[NODS], sol[NODS], s[NODS];


int main()
{
    long i, j, k, next, lev = 0;

    n = 0;
    while (scanf("%ld", &s[n++]) == 1)
        flag[--s[n - 1]]++;
    for (i = 0; i < n; i++)
        how[i] = flag[i] + 1;
    for (sum[0] = 0, i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + how[i - 1], how[i - 1] = 0;

    for (i = 0; i < n; i++)
        if (!flag[i])
            next = i, i = n;
    for (i = 0; i < n - 1; i++)
    {
        k = s[i];
        sol[sum[k] + how[k]++] = next;
        sol[sum[next] + how[next]++] = k;
        flag[k]--; flag[next]--;
        while (flag[++next]);
        if (k < next && !flag[k]) next = k;
    }
    for (sum[0] = 0, i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + how[i - 1];
    /* sortarea  */
    for (i = 0; i < n; i++)
        for (k = sum[i]; k < sum[i] + how[i]; k++)
            for (j = k + 1; j < sum[i] + how[i]; j++)
                if (sol[k] > sol[j])
                    next = sol[k], sol[k] = sol[j], sol[j] = next;

    for (i = 0; i < n; i++, printf("\n"))
    {
        printf("%ld: ", i + 1);
        for (k = sum[i]; k < sum[i] + how[i]; k++)
            printf("%ld ", sol[k] + 1);
    }
    return 0;
}