using System using System Collections Generic using System Linq using

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public class Parents
{
public int[] P;
public int[] W;
public int[] H;
private const int defaultCapacity = 10;
private int size;
public Parents(int max_n)
{
this.size = max_n;
this.P = new int[defaultCapacity];
this.W = new int[defaultCapacity];
this.H = new int[defaultCapacity];
for (int i = 0; i < defaultCapacity; ++i)
{
this.H[i] = -1;
}
}
public void Add(int newElement, int id)
{
this.size++;
P[this.size - 1] = id;
W[this.size - 1] = newElement;
}
public int GetLength(int id)
{
int count = 0;
while (this.P[id] != -1)
{
count++;
id = this.P[id];
}
return count;
}
public int GetFullLength()
{
int ret = 0;
for (int i = 0; i < this.size; ++i)
{
this.H[i] = GetLength(i);
ret += this.H[i];
}
return ret;
}
public void GetLength2(int id)
{
int first = id;
int count = 0;
while (this.H[id] == -1)
{
id = this.P[id];
count++;
}
count += this.H[id];
id = first;
while (this.H[id] == -1)
{
this.H[id] = count;
id = this.P[id];
count--;
}
}
public void GetFullLength2()
{
for (int i = 0; i < this.size; ++i)
{
GetLength2(i);
}
}
}
static void Main(string[] args)
{
int n = 8;
int[] input_p = { 1, -1, 1, 1, 2, 3, 0, 0 };
int[] input_w = { 7, 12, 11, 5, 4, 3, 7, 9 };
Parents M = new Parents(n);
for (int i = 0; i < n; ++i)
{
M.P[i] = input_p[i];
M.W[i] = input_w[i];
if (input_p[i] == -1)
{
M.H[i] = 0;
}
}
M.Add(15, 3);
M.GetFullLength2(); //O(n)
}
}
}