i have tried this problem several years....while preparing for contests and it's always WA and it's not at all the heardest of problems.....
i made an O (n log n) alg using heaps ....as usual
it's WA at test 2

could someone put some tests around??? i ageve my self some and nothing....bad
could somebody explain why??????????????:
1 2 3 2 3
my result:
1: 2 4
2: 1 3 6
3: 2 5
4: 1
5: 3
6: 2
AC result:
1: 2 4
2: 1 3 6
3: 2 5
4: 1
5: 1  //5 is not even conected to 1???????
6: 3




Edited by author 13.10.2006 04:08

Edited by author 13.10.2006 04:40

I checked everything 100 times but still can not understand what the problem is.(i wrote on Java)

has anyone done it in O(n)?

HELP!My algo:find the minimum,add the edge,sort and print,the first and the third step I use the heap.I don't think these matter.
My code:

#include<iostream>
using namespace std;
const int maxn = 7500;
int heap_size = 0, now = 0;
int heap[maxn + 1];
struct edge
{
    int neighbour;
    edge *pre;
}e[maxn + 1];
edge *tail[maxn + 1];
inline void swap(int i, int j)
{
    int temp;
    temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
    return;
}
void heap_up(int i)
{
    if (i == 1) return;
    int father = i / 2;
    if (heap[i] < heap[father])
    {
        swap(i, father);
        heap_up(father);
    }
    return;
}
void heap_down(int i)
{
    int left = i * 2;
    int right = left + 1;
    int least = i;
    if (left <= heap_size && heap[left] < heap[least]) least = left;
    if (right <= heap_size && heap[right] < heap[least]) least = right;
    if (least != i)
    {
        swap(i, least);
        heap_down(least);
    }
    return;
}
inline void heap_delete(int i)
{
    swap(i, heap_size--);
    heap_down(i);
    return;
}
inline void heap_insert(int key)
{
    heap[++heap_size] = key;
    heap_up(heap_size);
    return;
}
inline void connect(int u, int v)
{
    e[++now].neighbour = v;
    e[now].pre = tail[u];
    tail[u] = e + now;
    return;
}
int main()
{
    int son[maxn + 1] = { 0 }, code[maxn];
    int n = 1, i, u, v, temp;
    do
    {
        temp = 0;
        cin >> temp;
        if (temp)
        {
            code[n++] = temp;
            son[temp]++;
        }
    } while (temp);
    for (i = 1; i <= n; i++) if (!son[i]) heap_insert(i);
    for (i = 1; i <= n; i++) tail[i] = nullptr;
    for (i = 1; i < n; i++)
    {
        v = heap[1];
        heap_delete(1);
        u = code[i];
        if (!(--son[u])) heap_insert(u);
        connect(u, v);
        connect(v, u);
    }
    edge *p;
    heap_size = 0;
    for (i = 1; i <= n; i++)
    {
        cout << i << ":";
        for (p = tail[i]; p != nullptr; p = p->pre) heap_insert(p->neighbour);
        for (; heap_size; heap_delete(1)) cout << " " << heap[1];
        cout << endl;
    }
    return 0;
}

Edited by author 06.02.2015 21:40

Edited by author 07.02.2015 08:44

 As I said before I think java programs should get higher time limit. My java program gets TLE on test #4 or #5 285ms.
In my opinion my program runs in O(nlogn). Below I gave the code that gets TLE:



import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> lst = new ArrayList<>();
        int[] sorted;
        PriorityQueue<Integer>[] g;

        int[] degree = new int[8000];
        Arrays.fill(degree, 0);

        // O(n)
        while (sc.hasNextInt()) {
            int tt = sc.nextInt() - 1;
            lst.add(tt);
            degree[tt]++;
        }

        g = new PriorityQueue[lst.size() + 1];
        sorted = new int[lst.size() + 1];
        // O(n)
        for (int i = 0; i < lst.size() + 1; i++) {
            sorted[i] = i;
            g[i] = new PriorityQueue<>();
        }

        // find initial leaves O(nlogn)
        PriorityQueue<Integer> leaves = new PriorityQueue<>();
        for (Integer y : sorted) {
            if (degree[y] == 0) {
                leaves.add(y);
            }
        }

        // O(nlogn)
        for (int x : lst) {
            degree[x]--;

            int y = leaves.poll();

            g[x].add(y);
            g[y].add(x);

            if(degree[x] == 0){
                leaves.add(x);
            }

        }

        // O(nlogn)
        for (int i = 0; i < g.length; i++) {
            System.out.print((i + 1) + ":");
            while (!g[i].isEmpty()) {
                System.out.print(" " + (g[i].poll() + 1));
            }
            System.out.println("");
        }

    }
}





Edited by author 12.12.2014 23:17

- Do you know test 4 ?
- Any helpful tests ?
- If not, please pick bugs from my code. My algo: Find minimal, adjacent list, output sorted list. Tks a loooottttttt

Program Prufer_Code;
Type
        pnode = ^node;
        node = Record
         data:Longint;
         next:pnode;
End;

Var     adjList:Array[0..7500] of pnode;
        temp:pnode;
        A,C,minS:Array[0..7500] of Longint;
        n,i,j,s,p,q,m:Longint;
        fi:Text;
Procedure add(k:Longint;var x:pnode);
Var
        y,z:pnode;
Begin
        If (x=nil) then
         Begin
          new(x);
          x^.data:=k;
         End
        Else
         Begin
          new(y);
          y^.data:=k;
          y^.next:=x;
          x:=y;
         End;
End;

Begin

                n:=0;
                While not seekeof do
                 Begin
                  inc(n);
                  Read(A[n]);
                 End;

                For i:=1 to n+1 do
                 Begin
                  inc(C[i]);
                  inc(C[A[i]]);
                 End;
                dec(C[A[n+1]],2);
                p:=0;

                For i:=1 to n+1 do
                 If C[i]=1 then
                  Begin
                   inc(p);
                   minS[p]:=i;
                  End;

                For i:=1 to n do
                 Begin
                  q:=minS[1]; m:=1;
                  For j:=2 to p do
                   If minS[j]<q then
                    Begin
                     q:=minS[j];
                     m:=j;
                    End;
                  j:=q; minS[m]:=99999;


                  add(j,adjList[A[i]]);
                  add(A[i],adjList[j]);
                  dec(C[A[i]]);

                  If C[A[i]]=1 then
                   Begin
                    inc(p);
                    minS[p]:=A[i];
                   End;

                 End;

                For i:=1 to n+1 do
                 Begin
                  FillChar(C,sizeof(C),0);
                  temp:=adjList[i];
                  p:=0;
                  while temp<>nil do
                   Begin
                    inc(C[temp^.data]);
                    temp:=temp^.next;
                   End;
                  Write(i,': ');
                  For j:=1 to 7500 do
                   If C[j]=1 then Write(j,' ');
                  Writeln;
                 End;
End.

I've written the program for many times,but when I submited it,I always see "MLE" or "Wrong Answer",I've submitted it for more than 10 times!!!
Finally Accepted!!!

OK I've found that my heap is error,and I got MLE then.

Edited by author 04.03.2013 19:32


Edited by author 04.03.2013 19:32

Well, i got WA on it and then modified something and got Memory Limit Exceeded. I'm using a matrix of 7501*7501. I think i should make lists of neighbours?

I got WA on test 3.

I wonder that:
Are there any special tests in this problem?
OR
Is there anything special in the output task?

Just ask: If n=10, Can I output like this:
('...' Stands for some digits)
1: ...
...
9: ...
10: ...
Must I leave a space before '9' in order to make ':' in the same column?

Could anyone help me, please?

I got wa on test 2

I want to know if input is : 2 2
what should I output?

sorry my English is very poor

Don't forget about it ;)

Hi,

In the question they said that the last vertex left (or last vertex of given prufer code) should be equal to N or number of nodes in the graph. But its not like that somehow, so I changed N to total numbers in prufer code + 1. Then no more WA 1.

Varun

Edited by author 08.03.2010 06:55

I use a very simple algorithm..my code is very short..
*just (for i:=1 to n do)check if the number appears in the A set of numbers after i.
*set down the father of each number.
*Just output.

(i'm sorry that my English is really bad..)

var
  con,temp,i,j:longint;
  fin:array[1..7500]of boolean;
  b,a,fa:array[1..7500]of integer;
begin
  {$IFNDEF ONLINE_JUDGE}
  assign(input,'input.in');reset(input);
  assign(output,'output.out');rewritE(output);
  {$ENDIF}
  reaD(temp);
  con:=0;
  while temp<>0 do
    begin
      inc(con);
      a[con]:=temp;
      inc(b[temp]);
      read(temp);
    end;
  for i := 1 to con do
    for j := 1 to con+1 do
      if (not fin[j])and(b[j]=0) then
        begin
          fin[j]:=true;
          fa[j]:=a[i];
          deC(b[a[i]]);
          break;
        end;
  for i := 1 to con+1 do
    begin
      write(i,':');
      for j := 1 to con+1 do
        if (fa[j]=i)or(fa[i]=j) then
          write(' ',j);
      writeln;
    end;
end.

Edited by author 13.10.2009 15:09

Can you tell me an idea how to solve it in O(N) or in O(N*logN)
Thanks

for example for test: 8 7 4 6 3 6 8
my program writes:
1: 8
2: 7
3: 7 6
4: 5 6
5: 4
6: 4 3 8
7: 2 3
8: 1 6

which is correct, but i got WA#2

if i sort the result:
1: 8
2: 7
3: 6 7
4: 5 6
5: 4
6: 3 4 8
7: 2 3
8: 1 6

i get TL#5

i have got AC

Edited by author 18.06.2009 02:45

Edited by author 18.06.2009 05:09

Edited by author 18.06.2009 05:42

Edited by author 14.03.2009 00:58

Prufer code is not N-1!!! Its should be N-2, because the last number always N. For example if I will get the numbers: 1 1 1 1 1, its impossible to build this graph. About this possible to read here:
http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence