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[] A;
public int[] B;
private const int digital = 8;
private int size;
public Parents(int max_n)
{
this.size = max_n;
this.P = new int[digital];
this.A = new int[digital];
this.B = new int[digital];
for (int i = 0; i < digital; ++i)
{
this.B[i] = -1;
}
}
public void Add(int newElement, int id)
{
this.size++;
P[this.size - 1] = id;
A[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.B[i] = GetLength(i);
ret += this.B[i];
}
return ret;
}
public void GetLength2(int id)
{
int first = id;
int count = 0;
while (this.B[id] == -1)
{
id = this.P[id];
count++;
}
count += this.B[id];
id = first;
while (this.B[id] == -1)
{
this.B[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 = 6;
int[] input_p = { 1, -1, 1, 1, 2, 3 };
int[] input_a = { 7, 12, 11, 5, 4, 3 };
Parents M = new Parents(n);
for (int i = 0; i < n; ++i)
{
M.P[i] = input_p[i];
M.A[i] = input_a[i];
if (input_p[i] == -1)
{
M.B[i] = 0;
}
}
M.Add(15, 3);
M.GetFullLength2(); //O(n)
}
}
}