Computer Network Algorithm test

ComputerNetwork.cs

public static class ComputerNetwork
{
    public static void Run()
    {
        //var output = Network(new int[] { 0, 3, 4, 2, 6, 3 }, new int[] { 3, 1, 3, 3, 3, 5 });
        var output = Network(new int[] { 0, 4, 2, 2, 4 }, new int[] { 1, 3, 1, 3, 5 });
        //var output = Network(new int[] { 0, 4, 4, 2, 7, 6, 3 }, new int[] { 3, 5, 1, 3, 4, 3, 4 });

        Console.WriteLine($"output is : {output}");
    }

    private static int Network(int[] A, int[] B)
    {
        const int max = 90000;
        var all = A.Concat(B).Distinct().OrderBy(x => x).ToList();

        if (all.Any(x => x > max))
        {
            return 0;
        }

        var dict = new Dictionary<int, Node>();
        all.ForEach(x => dict.Add(x, new Node(self: x)));

        // find pairs of nodes connected by direct links
        for (var i = 0; i < dict.Count - 1; i++)
        {
            var node1 = dict[A[i]];
            var node2 = dict[B[i]];

            node1.Children.Add(node2);
            node2.Children.Add(node1);

            if (node1.Children.Count > 1000 || node2.Children.Count > 1000)
            {
                return 0;
            }
        }

        //foreach (var node in dict)
        //{
        //    Console.Write($"[{node.Key}] = | ");
        //    foreach (var child in node.Value.Children)
        //    {
        //        Console.Write($"{child.Self} | ");
        //    }
        //    Console.WriteLine($"{Environment.NewLine}--------");
        //}

        Connections = new Dictionary<Tuple<int, int>, int>();

        foreach (var i in all)
        {
            var current = dict[i];

            for (var j = 0; j < all.Count; j++)
            {
                var target = dict[j];
                if (current.Self != target.Self)
                {
                    Console.WriteLine($"--------------------------------------------");
                    var distance = FindDistance(current, target, current, new List<int>());
                    //if (distance % 2 != 0)
                    {
                        var link = new int[] { current.Self, target.Self }.OrderBy(x => x).ToList();
                        if (!Connections.ContainsKey(new Tuple<int, int>(link[0], link[1])))
                        {
                            Console.WriteLine($"{link[0]}-{link[1]}={distance}");
                            Connections.Add(new Tuple<int, int>(link[0], link[1]), distance);
                        }
                        else
                        {
                            Console.WriteLine($"{link[0]}-{link[1]}={distance} (updated)");
                            Connections[new Tuple<int, int>(link[0], link[1])] = distance;
                        }
                    }
                }
            }
        }

        foreach (var (key, value) in Connections)
        {
            Console.WriteLine($"{key.Item1}-{key.Item2}={value}");
        }

        return Connections.Count;
    }

    public static Dictionary<Tuple<int, int>, int> Connections { get; set; }

    private static int FindDistance(Node start, Node target, Node? parent, List<int> childrenVisited, int counter = 1)
    {
        Console.WriteLine($"calling findDistance {start.Self}, {target.Self}, {counter}, [{string.Join(", ", childrenVisited)}]");

        if (!start.Children.Any(x => x.Self.Equals(target.Self)))
        {
            childrenVisited.Add(start.Self);
            foreach (var child in start.Children.Where(x => !childrenVisited.Contains(x.Self)))
            {
                if (child.Self != parent?.Self)
                {
                    counter++;
                    Console.WriteLine($"loop [{start.Self}->{child.Self}] target[{target.Self}]={counter}");
                    return FindDistance(child, target, start, childrenVisited, counter);
                }
            }
        }

        Console.WriteLine($"link found start[{start.Self}] target[{target.Self}]={counter}");
        return counter;
    }
}

gistfile1.txt

You analyze the performance of a computer network. The network comprises nodes connected by peer-to-peer links. There are N links and N + 1 nodes. All pairs of nodes are (directly or indirectly) connected by links, and links don't form cycles. In other words, the network has a tree topology.
Your analysis shows that communication between two nodes performs much better if the number of links on the (shortest) route between the nodes is odd. Of course, the communication is fastest when the two nodes are connected by a direct link. But, amazingly, if the nodes communicate via 3, 5, 7, etc. links, communication is much faster than if the number of links to pass is even.
Now you wonder how this influences the overall network performance. There are N * (N + 1) / 2 different pairs of nodes. You need to compute how many of them are pairs of nodes connected via an odd number of links.
Nodes are numbered from 0 to N. Links are described by two arrays of integers, A and B, each containing N integers. For each 0 ≤ I < N, there is a link between nodes A[I] and B[I].
Write a function:
	class Solution { public int solution(int[] A, int[] B); }
that, given two arrays, A and B, consisting of N integers and describing the links, computes the number of pairs of nodes X and Y, such that 0 ≤ X < Y ≤ N, and X and Y are connected via an odd number of links.
For example, given N = 6 and the following arrays:
A[0] = 0 B[0] = 3 A[1] = 3 B[1] = 1 A[2] = 4 B[2] = 3 A[3] = 2 B[3] = 3 A[4] = 6 B[4] = 3 A[5] = 3 B[5] = 5

the function should return 6, since:
	• there are six pairs of nodes connected by direct links, and
	• all other pairs of nodes are connected via two links.
Given N = 5 and the following arrays:
A[0] = 0 B[0] = 1 A[1] = 4 B[1] = 3 A[2] = 2 B[2] = 1 A[3] = 2 B[3] = 3 A[4] = 4 B[4] = 5

the function should return 9, since:
	• there are five pairs of nodes connected by direct links,
	• there are three pairs of nodes connected via three links, and
	• there is one pair of nodes connected via five links.
Given N = 7 and the following arrays:
A[0] = 0 B[0] = 3 A[1] = 4 B[1] = 5 A[2] = 4 B[2] = 1 A[3] = 2 B[3] = 3 A[4] = 7 B[4] = 4 A[5] = 6 B[5] = 3 A[6] = 3 B[6] = 4

the function should return 16, since:
	• there are seven pairs of nodes connected by direct links, and
	• there are nine pairs of nodes connected via three links.
Write an efficient algorithm for the following assumptions:
	• N is an integer within the range [0..90,000];
	• each element of arrays A and B is an integer within the range [0..N];
	• the network has a tree topology;
	• any pair of nodes is connected via no more than 1000 links.

Program.cs

using System.Diagnostics;

var stopWatch = new Stopwatch();
stopWatch.Start();

ComputerNetwork.Run();

var ts = stopWatch.Elapsed;

// Format and display the TimeSpan value.
string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:000}",
    ts.Hours, ts.Minutes, ts.Seconds,
    ts.Milliseconds);
Console.WriteLine("RunTime " + elapsedTime);