Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Diameter Minimization Solution

Yashwant Parihar, June 2, 2023May 28, 2024

In this post, we will solve HackerRank Diameter Minimization Problem Solution.

We define the diameter of a strongly-connected oriented graph, G = (V,E), as the minimum integer & such that for each u, v EG there is a path from u to v of length <d (recall that a path’s length is its number of edges).
Given two integers, n and m. build a strongly-connected oriented graph with n vertices where each vertex has outdegree m and the graph’s diameter is as small as possible (see the Scoring section below for more detail). Then print the graph according to the Output Format specified below.
Here’s a sample strongly-connected oriented graph with 3 nodes, whose outdegree is 2 and diameter is 1.

Note: Cycles and multiple edges between vertices are allowed.
Input Format
Two space-separated integers describing the respective values of n (the number of vertices) and m (the outdegree of each vertex).

Scoring
We denote the diameter of your graph as d and the diameter of the graph in the author’s solution as 8. Your score for each test case (as a real number from 0 to 1)

Output Format
First, print an integer denoting the diameter of your graph on a new line.
Next, print n lines where each line i (0 < i < n) contains m space-separated integers in the inclusive range from 0 ton – 1 describing the endpoints for each of vertex i’s outbound edges.

Sample Input 0

5 2

Sample Output 0

2
1 4
2 0
3 1
4 2
0 3

Explanation 0
The diagram below depicts a strongly-connected oriented graph with n = 5 nodes where each node has an outdegree of m = 2

The diameter of this graph is d = 2, which is minimal as the outdegree of each node must be m. We cannot construct a graph with a smaller diameter of d = 1 because it requires an outbound edge from each vertex to each other vertex in the graph (so the outdegree of that graph would be n-1).

HackerRank Diameter Minimization Problem Solution
HackerRank Diameter Minimization Problem Solution

Diameter Minimization C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

int calcBest(int n, int m) {
    int d = 0;
    int onD = 1;
    int cn = 1;
    while (cn < n) {
        onD *= m;
        ++d;
        cn += onD;
    }
    return d;
}

const int maxn = 1005;
int g[maxn][maxn];
int n, m;

int dist[maxn];
int calcDiam(int s) {
    fill(dist, dist + n, inf);

    vector<int> q;
    dist[s] = 0;
    q.push_back(s);
    forn (ii, sz(q)) {
        int u = q[ii];
        forn (i, m) {
            int v = g[u][i];
            if (dist[v] < inf)
                continue;
            dist[v] = dist[u] + 1;
            q.push_back(v);
        }
    }

    if (sz(q) < n)
        return inf;
    return dist[q.back()];
}

int main() {
    cin >> n >> m;
    forn (i, n) {
        forn (j, m)
            g[i][j] = (i * m + j) % n;
    }
    int diam = 0;
    forn (i, n)
        diam = max(diam, calcDiam(i));
    int best = calcBest(n, m);
    //cerr << "best " << best << '\n';
    assert(diam <= best + 1);
    assert(diam >= best);

    cout << diam << '\n';
    forn (i, n) {
        forn (j, m)
            cout << g[i][j] << ' ';
        cout << '\n';
    }
}

Diameter Minimization C Sharp Solution

	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	using System.Linq;
	using System.Text;
	using static System.Math;
	using static System.Console;
	using static HackerRankUtils;

	public class Solution
	{
		#region Variables

		int m;
		int n;
		int BestDiameter = int.MaxValue;
		bool toplevel;
		Graph BestGraph = null;

		public static Dictionary<Tuple<int, int>, Solution> memo = new Dictionary<Tuple<int, int>, Solution>();
		public static readonly Random random = new Random(unchecked((int)0xDEADBEEF));
		public static readonly Dictionary<int, List<Case>> cases = new Dictionary<int, List<Case>>();

		#endregion

		#region Constructor
		static void Main(string[] args)
		{
			var sw = new Stopwatch();
			sw.Start();

			var input = ReadLine().Split(' ');
			var n = int.Parse(input[0]);
			var m = int.Parse(input[1]);

			var sol = new Solution(n, m, true);

			LaunchTimer(() =>
			{
				Report(sol);
				return true;
			}, TimeLimit);

			Setup();
			var g = sol.Solve();
			Report(sol);

#if DEBUG
			WriteLine(sw.Elapsed);
#endif
		}

		static void Report(Solution sol)
		{
			var g = sol.BestGraph;
			WriteLine(sol.BestDiameter);

			var list = new List<int>();
			for (int i = 0; i < sol.n; i++)
			{
				list.Clear();
				list.AddRange(g[i]);
				while (list.Count < sol.m)
					list.Add(list[0]);
				WriteLine(string.Join(" ", list));
			}
		}
		
		public static void Test()
		{
			for (int i=2; i<1000; i++)
				for (int j=2; j<=5 && j<=i; j++)
				{
					var sol = new Solution(i, j);
					sol.Solve();
				}
		}

		public Solution(int n, int m, bool toplevel=false)
		{
			this.n = n;
			this.m = m;
			this.toplevel = toplevel;
		}
		#endregion

		public Graph Solve()
		{
			var g = SolveCore();
			if (g != null)
				RecordGraph(g);
			return BestGraph;
		}

		public Graph SolveCore()
		{
			if (m >= n - 1)
				return Graph.Complete(n);

            
			if (m==2)
            {
				RecordGraph(Graph.CycleGraph(n, m, true));
            }
            
			// Case Analysis
			if (cases.ContainsKey(n))
			{
				foreach(var c in cases[n])
				{
					if (m < c.Degree)
						continue;

					var g = c.Action();
					Debug.Assert(g.Diameter() == c.Diameter);

					// Set the graph as an upper bound
					RecordGraph(g);
				}
			}

			// Divide and Conquer
			if (n % 2 == 0 && m !=2)
			{
				var sol = Recurse(n / 2, m - 1);
				// Diameter + 1, Degree + 1
				var g = Graph.Product(sol.BestGraph, Graph.K2);
				Debug.Assert(g.Diameter() == sol.BestDiameter + 1);
				RecordGraph(g);
			}

            RecordGraph(Graph.ConnectedGraph(n,m));
            /*
            // Iterate through multiple random graphs
			var limit = toplevel ? RandomIterationsTop : RandomIterations;
			for (int i = 0; i < limit; i++)
			{
				RecordGraph(Graph.RandomGraph(n, m, true));
				RecordGraph(Graph.RandomGraph(n, m, false));
			}*/

			// null means we are unsure;
			return null;
		}


		public static Solution Recurse(int n, int m)
		{
			var tup = new Tuple<int, int>(n, m);
			if (memo.ContainsKey(tup))
				return memo[tup];
			var sol = new Solution(n / 2, 2);
			sol.Solve();
			memo[tup] = sol;
			return sol;
		}


		public void Attempt4()
		{
			if (n % 2 != 0) return;

			var sol = Recurse(n / 2, 2);
			var g = Graph.Product(sol.BestGraph, Graph.K2, false);
			RecordGraph(g);
		}

		public void Attempt5()
		{
			if (n % 2 != 0) return;

			var sol = Recurse(n / 2, 2);
			var g0 = sol.BestGraph;
			var g = Graph.Product(g0, Graph.K2, true);
			RecordGraph(g);
		}


		public void RecordGraph(Graph g)
		{
			var diameter = g.Diameter(BestDiameter);

            foreach(var e in g.g)
            {
                foreach(var v in e)
                    if (v>=g.g.Length || v<0) return;
            }
            
            if (g.g.Length < n) return;
            
			if (BestGraph==null || diameter < BestDiameter)
			{
				BestGraph = g;
				BestDiameter = diameter;
			}
		}


		#region Case Analysis 
		public static void Setup()
		{
			AddCase(18, 3, 3, () => Graph.Graph33(18));
			AddCase(16, 4, 2, () => Graph.G8(2));
			AddCase(24, 5, 2, () => Graph.G8(3));
			AddCase(4, 2, 2, () => Graph.CubeGraph(2));
			AddCase(16, 4, 4, () => Graph.CubeGraph(4));
			AddCase(32, 5, 5, () => Graph.CubeGraph(5));
			
			// K3,3 = C6(1,3)  
			AddGraph(6, 3, 2, new[,] { { 0, 1 }, { 0, 3 }, { 0, 5 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 4, 5 } });

			// C8(1,4)  
			AddGraph(8, 3, 2, new[,] { { 0, 1 }, { 0, 4 }, { 0, 7 }, { 1, 2 }, { 1, 5 }, { 2, 3 }, { 2, 6 }, { 3, 4 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } });

			// P  
			AddGraph(10, 3, 2, new[,] { { 0, 1 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 7 }, { 3, 4 }, { 3, 8 }, { 4, 9 }, { 5, 7 }, { 5, 8 }, { 6, 8 }, { 6, 9 }, { 7, 9 } });

			// C = Cml8(2:0,3)  
			//AddGraph(8, 3, 3, new[,] { { 0, 1 }, { 0, 3 }, { 0, 7 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 6, 7 } });

			// C10(1,5)  
			AddGraph(10, 3, 3, new[,] { { 0, 1 }, { 0, 5 }, { 0, 9 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 7 }, { 3, 4 }, { 3, 8 }, { 4, 5 }, { 4, 9 }, { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } });

			// C12(1,6)  
			AddGraph(12, 3, 3, new[,] { { 0, 1 }, { 0, 11 }, { 0, 6 }, { 1, 2 }, { 1, 7 }, { 2, 3 }, { 2, 8 }, { 3, 4 }, { 3, 9 }, { 4, 10 }, { 4, 5 }, { 5, 11 }, { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 } });

			// PP7(1,3) K2  
			//AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 7, 10 }, { 7, 11 }, { 8, 11 }, { 8, 12 }, { 9, 12 }, { 9, 13 }, { 10, 13 } });

			// PP7(1,2) K2  
			//AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 7, 12 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 9, 11 }, { 10, 12 }, { 11, 13 } });

			// Heawood  
			AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 13 }, { 0, 5 }, { 1, 10 }, { 1, 2 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 4 }, { 4, 5 }, { 4, 9 }, { 5, 6 }, { 6, 11 }, { 6, 7 }, { 7, 8 }, { 8, 13 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 } });

			// O = C6(1,2)  
			AddGraph(6, 4, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 3 }, { 1, 5 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, { 3, 5 }, { 4, 5 } });

			// K4,4 = C8(1,3)  
			AddGraph(8, 4, 2, new[,] { { 0, 1 }, { 0, 3 }, { 0, 5 }, { 0, 7 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 2, 3 }, { 2, 5 }, { 2, 7 }, { 3, 4 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 6, 7 } });

			// K3 × K3  
			AddGraph(9, 4, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 7 }, { 2, 5 }, { 2, 8 }, { 3, 4 }, { 3, 5 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 8 }, { 6, 7 }, { 6, 8 }, { 7, 8 } });

			// C11(1,3)  
			AddGraph(11, 4, 2, new[,] { { 0, 1 }, { 0, 10 }, { 0, 3 }, { 0, 8 }, { 1, 2 }, { 1, 4 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 5, 8 }, { 6, 7 }, { 6, 9 }, { 7, 10 }, { 7, 8 }, { 8, 9 }, { 9, 10 } });

			// Cml15(5:1,4:2,5:3,7:4,4:4,7)  
			AddGraph(15, 4, 2, new[,] { { 0, 1 }, { 0, 11 }, { 0, 14 }, { 0, 8 }, { 1, 2 }, { 1, 5 }, { 1, 9 }, { 2, 12 }, { 2, 3 }, { 2, 7 }, { 3, 10 }, { 3, 14 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 4, 8 }, { 5, 13 }, { 5, 6 }, { 6, 10 }, { 6, 14 }, { 6, 7 }, { 7, 12 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 9, 13 }, { 10, 11 }, { 11, 12 }, { 12, 13 }, { 13, 14 } });

			// C14(1,7)  
			AddGraph(14, 3, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 6, 7 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 } });

			// C16(1,8)  
			AddGraph(16, 3, 4, new[,] { { 0, 1 }, { 0, 15 }, { 0, 8 }, { 1, 2 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 3, 11 }, { 3, 4 }, { 4, 12 }, { 4, 5 }, { 5, 13 }, { 5, 6 }, { 6, 14 }, { 6, 7 }, { 7, 15 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 }, { 13, 14 }, { 14, 15 } });

			// PP11(1,3) K2  
			AddGraph(22, 3, 4, new[,] { { 0, 1 }, { 0, 10 }, { 0, 11 }, { 1, 12 }, { 1, 2 }, { 2, 13 }, { 2, 3 }, { 3, 14 }, { 3, 4 }, { 4, 15 }, { 4, 5 }, { 5, 16 }, { 5, 6 }, { 6, 17 }, { 6, 7 }, { 7, 18 }, { 7, 8 }, { 8, 19 }, { 8, 9 }, { 9, 10 }, { 9, 20 }, { 10, 21 }, { 11, 14 }, { 11, 19 }, { 12, 15 }, { 12, 20 }, { 13, 16 }, { 13, 21 }, { 14, 17 }, { 15, 18 }, { 16, 19 }, { 17, 20 }, { 18, 21 } });

			// McGee = Cml24(3:1,12:2,7:0,17)  
			AddGraph(24, 3, 4, new[,] { { 0, 1 }, { 0, 17 }, { 0, 23 }, { 1, 13 }, { 1, 2 }, { 2, 3 }, { 2, 9 }, { 3, 20 }, { 3, 4 }, { 4, 16 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 23 }, { 6, 7 }, { 7, 19 }, { 7, 8 }, { 8, 15 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 10, 22 }, { 11, 12 }, { 11, 18 }, { 12, 13 }, { 13, 14 }, { 14, 15 }, { 14, 21 }, { 15, 16 }, { 16, 17 }, { 17, 18 }, { 18, 19 }, { 19, 20 }, { 20, 21 }, { 21, 22 }, { 22, 23 } });

			// Tutte-Coxeter = Cml30(6:1,17:2,21:3,7)  
			AddGraph(30, 3, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 29 }, { 1, 18 }, { 1, 2 }, { 2, 23 }, { 2, 3 }, { 3, 10 }, { 3, 4 }, { 4, 27 }, { 4, 5 }, { 5, 14 }, { 5, 6 }, { 6, 19 }, { 6, 7 }, { 7, 24 }, { 7, 8 }, { 8, 29 }, { 8, 9 }, { 9, 10 }, { 9, 16 }, { 10, 11 }, { 11, 12 }, { 11, 20 }, { 12, 13 }, { 12, 25 }, { 13, 14 }, { 14, 15 }, { 15, 16 }, { 15, 22 }, { 16, 17 }, { 17, 18 }, { 17, 26 }, { 18, 19 }, { 19, 20 }, { 20, 21 }, { 21, 22 }, { 21, 28 }, { 22, 23 }, { 23, 24 }, { 24, 25 }, { 25, 26 }, { 26, 27 }, { 27, 28 }, { 28, 29 } });

			// K2 × K3,3  
			AddGraph(12, 4, 3, new[,] { { 0, 1 }, { 0, 10 }, { 0, 2 }, { 0, 6 }, { 1, 11 }, { 1, 3 }, { 1, 7 }, { 2, 3 }, { 2, 4 }, { 2, 8 }, { 3, 5 }, { 3, 9 }, { 4, 10 }, { 4, 5 }, { 4, 6 }, { 5, 11 }, { 5, 7 }, { 6, 7 }, { 6, 8 }, { 7, 9 }, { 8, 10 }, { 8, 9 }, { 9, 11 }, { 10, 11 } });

			// K2 × P  
			AddGraph(20, 4, 3, new[,] { { 0, 1 }, { 0, 10 }, { 0, 2 }, { 0, 8 }, { 1, 11 }, { 1, 3 }, { 1, 9 }, { 2, 12 }, { 2, 3 }, { 2, 4 }, { 3, 13 }, { 3, 5 }, { 4, 14 }, { 4, 5 }, { 4, 6 }, { 5, 15 }, { 5, 7 }, { 6, 16 }, { 6, 7 }, { 6, 8 }, { 7, 17 }, { 7, 9 }, { 8, 18 }, { 8, 9 }, { 9, 19 }, { 10, 11 }, { 10, 14 }, { 10, 16 }, { 11, 15 }, { 11, 17 }, { 12, 13 }, { 12, 16 }, { 12, 18 }, { 13, 17 }, { 13, 19 }, { 14, 15 }, { 14, 18 }, { 15, 19 }, { 16, 17 }, { 18, 19 } });

			// Moebius D  
			//AddGraph(20, 4, 3, new[,] { { 0, 10 }, { 0, 16 }, { 0, 19 }, { 0, 4 }, { 1, 11 }, { 1, 19 }, { 1, 2 }, { 1, 3 }, { 2, 12 }, { 2, 18 }, { 2, 6 }, { 3, 13 }, { 3, 4 }, { 3, 5 }, { 4, 14 }, { 4, 8 }, { 5, 15 }, { 5, 6 }, { 5, 7 }, { 6, 10 }, { 6, 16 }, { 7, 17 }, { 7, 8 }, { 7, 9 }, { 8, 12 }, { 8, 18 }, { 9, 10 }, { 9, 11 }, { 9, 19 }, { 10, 14 }, { 11, 12 }, { 11, 13 }, { 12, 16 }, { 13, 14 }, { 13, 15 }, { 14, 18 }, { 15, 16 }, { 15, 17 }, { 17, 18 }, { 17, 19 } });

			// PP7(1,2,3) K3  
			AddGraph(21, 4, 3, new[,] { { 0, 1 }, { 0, 14 }, { 0, 6 }, { 0, 7 }, { 1, 15 }, { 1, 2 }, { 1, 8 }, { 2, 16 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 17 }, { 3, 4 }, { 4, 11 }, { 4, 18 }, { 4, 5 }, { 5, 12 }, { 5, 19 }, { 5, 6 }, { 6, 13 }, { 6, 20 }, { 7, 12 }, { 7, 14 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 9, 11 }, { 9, 16 }, { 10, 12 }, { 10, 17 }, { 11, 13 }, { 11, 18 }, { 12, 19 }, { 13, 20 }, { 14, 17 }, { 14, 18 }, { 15, 18 }, { 15, 19 }, { 16, 19 }, { 16, 20 }, { 17, 20 } });

			// (4,6)-cage  
			AddGraph(26, 4, 3, new[,] { { 0, 1 }, { 0, 17 }, { 0, 25 }, { 0, 5 }, { 1, 10 }, { 1, 2 }, { 1, 22 }, { 2, 19 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 24 }, { 3, 4 }, { 4, 21 }, { 4, 5 }, { 4, 9 }, { 5, 14 }, { 5, 6 }, { 6, 11 }, { 6, 23 }, { 6, 7 }, { 7, 16 }, { 7, 8 }, { 8, 13 }, { 8, 25 }, { 8, 9 }, { 9, 10 }, { 9, 18 }, { 10, 11 }, { 10, 15 }, { 11, 12 }, { 11, 20 }, { 12, 13 }, { 12, 17 }, { 13, 14 }, { 13, 22 }, { 14, 15 }, { 14, 19 }, { 15, 16 }, { 15, 24 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 18, 19 }, { 18, 23 }, { 19, 20 }, { 20, 21 }, { 20, 25 }, { 21, 22 }, { 22, 23 }, { 23, 24 }, { 24, 25 } });

			// PP7(1,2,3,2) C4  
			AddGraph(28, 4, 3, new[,] { { 0, 1 }, { 0, 21 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 22 }, { 1, 8 }, { 2, 23 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 24 }, { 3, 4 }, { 4, 11 }, { 4, 25 }, { 4, 5 }, { 5, 12 }, { 5, 26 }, { 5, 6 }, { 6, 13 }, { 6, 27 }, { 7, 12 }, { 7, 14 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 9, 11 }, { 9, 16 }, { 10, 12 }, { 10, 17 }, { 11, 13 }, { 11, 18 }, { 12, 19 }, { 13, 20 }, { 14, 17 }, { 14, 18 }, { 14, 21 }, { 15, 18 }, { 15, 19 }, { 15, 22 }, { 16, 19 }, { 16, 20 }, { 16, 23 }, { 17, 20 }, { 17, 24 }, { 18, 25 }, { 19, 26 }, { 20, 27 }, { 21, 23 }, { 21, 26 }, { 22, 24 }, { 22, 27 }, { 23, 25 }, { 24, 26 }, { 25, 27 } });

			// PP9(1,3) K2 U PP9(2,4) K2  
			AddGraph(18, 5, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 7 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 3 }, { 1, 8 }, { 2, 11 }, { 2, 3 }, { 2, 4 }, { 3, 12 }, { 3, 4 }, { 3, 5 }, { 4, 13 }, { 4, 5 }, { 4, 6 }, { 5, 14 }, { 5, 6 }, { 5, 7 }, { 6, 15 }, { 6, 7 }, { 6, 8 }, { 7, 16 }, { 7, 8 }, { 8, 17 }, { 9, 12 }, { 9, 13 }, { 9, 14 }, { 9, 15 }, { 10, 13 }, { 10, 14 }, { 10, 15 }, { 10, 16 }, { 11, 14 }, { 11, 15 }, { 11, 16 }, { 11, 17 }, { 12, 15 }, { 12, 16 }, { 12, 17 }, { 13, 16 }, { 13, 17 }, { 14, 17 } });

			// D  
			AddGraph(20, 3, 5, new[,] { { 0, 16 }, { 0, 19 }, { 0, 4 }, { 1, 19 }, { 1, 2 }, { 1, 3 }, { 2, 18 }, { 2, 6 }, { 3, 4 }, { 3, 5 }, { 4, 8 }, { 5, 6 }, { 5, 7 }, { 6, 10 }, { 7, 8 }, { 7, 9 }, { 8, 12 }, { 9, 10 }, { 9, 11 }, { 10, 14 }, { 11, 12 }, { 11, 13 }, { 12, 16 }, { 13, 14 }, { 13, 15 }, { 14, 18 }, { 15, 16 }, { 15, 17 }, { 17, 18 }, { 17, 19 } });

			// C × K2  
			AddGraph(16, 4, 4, new[,] { { 0, 1 }, { 0, 3 }, { 0, 7 }, { 0, 8 }, { 1, 2 }, { 1, 6 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 2, 5 }, { 3, 11 }, { 3, 4 }, { 4, 12 }, { 4, 5 }, { 4, 7 }, { 5, 13 }, { 5, 6 }, { 6, 14 }, { 6, 7 }, { 7, 15 }, { 8, 11 }, { 8, 15 }, { 8, 9 }, { 9, 10 }, { 9, 14 }, { 10, 11 }, { 10, 13 }, { 11, 12 }, { 12, 13 }, { 12, 15 }, { 13, 14 }, { 14, 15 } });

			// C5 × C5  
			AddGraph(25, 4, 4, new[,] { { 0, 1 }, { 0, 20 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 21 }, { 1, 6 }, { 2, 22 }, { 2, 3 }, { 2, 7 }, { 3, 23 }, { 3, 4 }, { 3, 8 }, { 4, 24 }, { 4, 9 }, { 5, 10 }, { 5, 6 }, { 5, 9 }, { 6, 11 }, { 6, 7 }, { 7, 12 }, { 7, 8 }, { 8, 13 }, { 8, 9 }, { 9, 14 }, { 10, 11 }, { 10, 14 }, { 10, 15 }, { 11, 12 }, { 11, 16 }, { 12, 13 }, { 12, 17 }, { 13, 14 }, { 13, 18 }, { 14, 19 }, { 15, 16 }, { 15, 19 }, { 15, 20 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 17, 22 }, { 18, 19 }, { 18, 23 }, { 19, 24 }, { 20, 21 }, { 20, 24 }, { 21, 22 }, { 22, 23 }, { 23, 24 } });

			// PP7(1,3) K2 × K2  
			//AddGraph(28, 4, 4, new[,] { { 0, 1 }, { 0, 14 }, { 0, 6 }, { 0, 7 }, { 1, 15 }, { 1, 2 }, { 1, 8 }, { 2, 16 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 17 }, { 3, 4 }, { 4, 11 }, { 4, 18 }, { 4, 5 }, { 5, 12 }, { 5, 19 }, { 5, 6 }, { 6, 13 }, { 6, 20 }, { 7, 10 }, { 7, 11 }, { 7, 21 }, { 8, 11 }, { 8, 12 }, { 8, 22 }, { 9, 12 }, { 9, 13 }, { 9, 23 }, { 10, 13 }, { 10, 24 }, { 11, 25 }, { 12, 26 }, { 13, 27 }, { 14, 15 }, { 14, 20 }, { 14, 21 }, { 15, 16 }, { 15, 22 }, { 16, 17 }, { 16, 23 }, { 17, 18 }, { 17, 24 }, { 18, 19 }, { 18, 25 }, { 19, 20 }, { 19, 26 }, { 20, 27 }, { 21, 24 }, { 21, 25 }, { 22, 25 }, { 22, 26 }, { 23, 26 }, { 23, 27 }, { 24, 27 } });

			// Heawood × K2  
			AddGraph(28, 4, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 14 }, { 0, 5 }, { 1, 10 }, { 1, 15 }, { 1, 2 }, { 2, 16 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 17 }, { 3, 4 }, { 4, 18 }, { 4, 5 }, { 4, 9 }, { 5, 19 }, { 5, 6 }, { 6, 11 }, { 6, 20 }, { 6, 7 }, { 7, 21 }, { 7, 8 }, { 8, 13 }, { 8, 22 }, { 8, 9 }, { 9, 10 }, { 9, 23 }, { 10, 11 }, { 10, 24 }, { 11, 12 }, { 11, 25 }, { 12, 13 }, { 12, 26 }, { 13, 27 }, { 14, 15 }, { 14, 19 }, { 14, 27 }, { 15, 16 }, { 15, 24 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 17, 26 }, { 18, 19 }, { 18, 23 }, { 19, 20 }, { 20, 21 }, { 20, 25 }, { 21, 22 }, { 22, 23 }, { 22, 27 }, { 23, 24 }, { 24, 25 }, { 25, 26 }, { 26, 27 } });

			// PP9(1,2,3,4) C4  
			AddGraph(36, 4, 4, new[,] { { 0, 1 }, { 0, 27 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 28 }, { 2, 11 }, { 2, 29 }, { 2, 3 }, { 3, 12 }, { 3, 30 }, { 3, 4 }, { 4, 13 }, { 4, 31 }, { 4, 5 }, { 5, 14 }, { 5, 32 }, { 5, 6 }, { 6, 15 }, { 6, 33 }, { 6, 7 }, { 7, 16 }, { 7, 34 }, { 7, 8 }, { 8, 17 }, { 8, 35 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 11, 13 }, { 11, 20 }, { 12, 14 }, { 12, 21 }, { 13, 15 }, { 13, 22 }, { 14, 16 }, { 14, 23 }, { 15, 17 }, { 15, 24 }, { 16, 25 }, { 17, 26 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 28, 32 }, { 28, 33 }, { 29, 33 }, { 29, 34 }, { 30, 34 }, { 30, 35 }, { 31, 35 } });

			// PP9(1,2,3,4,2) C5  
			AddGraph(45, 4, 4, new[,] { { 0, 1 }, { 0, 36 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 37 }, { 2, 11 }, { 2, 3 }, { 2, 38 }, { 3, 12 }, { 3, 39 }, { 3, 4 }, { 4, 13 }, { 4, 40 }, { 4, 5 }, { 5, 14 }, { 5, 41 }, { 5, 6 }, { 6, 15 }, { 6, 42 }, { 6, 7 }, { 7, 16 }, { 7, 43 }, { 7, 8 }, { 8, 17 }, { 8, 44 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 11, 13 }, { 11, 20 }, { 12, 14 }, { 12, 21 }, { 13, 15 }, { 13, 22 }, { 14, 16 }, { 14, 23 }, { 15, 17 }, { 15, 24 }, { 16, 25 }, { 17, 26 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 27, 36 }, { 28, 32 }, { 28, 33 }, { 28, 37 }, { 29, 33 }, { 29, 34 }, { 29, 38 }, { 30, 34 }, { 30, 35 }, { 30, 39 }, { 31, 35 }, { 31, 40 }, { 32, 41 }, { 33, 42 }, { 34, 43 }, { 35, 44 }, { 36, 38 }, { 36, 43 }, { 37, 39 }, { 37, 44 }, { 38, 40 }, { 39, 41 }, { 40, 42 }, { 41, 43 }, { 42, 44 } });

			// PP11(1,2,4,3,5) C5  
			AddGraph(55, 4, 4, new[,] { { 0, 1 }, { 0, 10 }, { 0, 11 }, { 0, 44 }, { 1, 12 }, { 1, 2 }, { 1, 45 }, { 2, 13 }, { 2, 3 }, { 2, 46 }, { 3, 14 }, { 3, 4 }, { 3, 47 }, { 4, 15 }, { 4, 48 }, { 4, 5 }, { 5, 16 }, { 5, 49 }, { 5, 6 }, { 6, 17 }, { 6, 50 }, { 6, 7 }, { 7, 18 }, { 7, 51 }, { 7, 8 }, { 8, 19 }, { 8, 52 }, { 8, 9 }, { 9, 10 }, { 9, 20 }, { 9, 53 }, { 10, 21 }, { 10, 54 }, { 11, 13 }, { 11, 20 }, { 11, 22 }, { 12, 14 }, { 12, 21 }, { 12, 23 }, { 13, 15 }, { 13, 24 }, { 14, 16 }, { 14, 25 }, { 15, 17 }, { 15, 26 }, { 16, 18 }, { 16, 27 }, { 17, 19 }, { 17, 28 }, { 18, 20 }, { 18, 29 }, { 19, 21 }, { 19, 30 }, { 20, 31 }, { 21, 32 }, { 22, 26 }, { 22, 29 }, { 22, 33 }, { 23, 27 }, { 23, 30 }, { 23, 34 }, { 24, 28 }, { 24, 31 }, { 24, 35 }, { 25, 29 }, { 25, 32 }, { 25, 36 }, { 26, 30 }, { 26, 37 }, { 27, 31 }, { 27, 38 }, { 28, 32 }, { 28, 39 }, { 29, 40 }, { 30, 41 }, { 31, 42 }, { 32, 43 }, { 33, 36 }, { 33, 41 }, { 33, 44 }, { 34, 37 }, { 34, 42 }, { 34, 45 }, { 35, 38 }, { 35, 43 }, { 35, 46 }, { 36, 39 }, { 36, 47 }, { 37, 40 }, { 37, 48 }, { 38, 41 }, { 38, 49 }, { 39, 42 }, { 39, 50 }, { 40, 43 }, { 40, 51 }, { 41, 52 }, { 42, 53 }, { 43, 54 }, { 44, 49 }, { 44, 50 }, { 45, 50 }, { 45, 51 }, { 46, 51 }, { 46, 52 }, { 47, 52 }, { 47, 53 }, { 48, 53 }, { 48, 54 }, { 49, 54 } });

			// PP13(1,5,4,2,3,6) C6  
			AddGraph(78, 4, 4, new[,] { { 0, 1 }, { 0, 12 }, { 0, 13 }, { 0, 65 }, { 1, 14 }, { 1, 2 }, { 1, 66 }, { 2, 15 }, { 2, 3 }, { 2, 67 }, { 3, 16 }, { 3, 4 }, { 3, 68 }, { 4, 17 }, { 4, 5 }, { 4, 69 }, { 5, 18 }, { 5, 6 }, { 5, 70 }, { 6, 19 }, { 6, 7 }, { 6, 71 }, { 7, 20 }, { 7, 72 }, { 7, 8 }, { 8, 21 }, { 8, 73 }, { 8, 9 }, { 9, 10 }, { 9, 22 }, { 9, 74 }, { 10, 11 }, { 10, 23 }, { 10, 75 }, { 11, 12 }, { 11, 24 }, { 11, 76 }, { 12, 25 }, { 12, 77 }, { 13, 18 }, { 13, 21 }, { 13, 26 }, { 14, 19 }, { 14, 22 }, { 14, 27 }, { 15, 20 }, { 15, 23 }, { 15, 28 }, { 16, 21 }, { 16, 24 }, { 16, 29 }, { 17, 22 }, { 17, 25 }, { 17, 30 }, { 18, 23 }, { 18, 31 }, { 19, 24 }, { 19, 32 }, { 20, 25 }, { 20, 33 }, { 21, 34 }, { 22, 35 }, { 23, 36 }, { 24, 37 }, { 25, 38 }, { 26, 30 }, { 26, 35 }, { 26, 39 }, { 27, 31 }, { 27, 36 }, { 27, 40 }, { 28, 32 }, { 28, 37 }, { 28, 41 }, { 29, 33 }, { 29, 38 }, { 29, 42 }, { 30, 34 }, { 30, 43 }, { 31, 35 }, { 31, 44 }, { 32, 36 }, { 32, 45 }, { 33, 37 }, { 33, 46 }, { 34, 38 }, { 34, 47 }, { 35, 48 }, { 36, 49 }, { 37, 50 }, { 38, 51 }, { 39, 41 }, { 39, 50 }, { 39, 52 }, { 40, 42 }, { 40, 51 }, { 40, 53 }, { 41, 43 }, { 41, 54 }, { 42, 44 }, { 42, 55 }, { 43, 45 }, { 43, 56 }, { 44, 46 }, { 44, 57 }, { 45, 47 }, { 45, 58 }, { 46, 48 }, { 46, 59 }, { 47, 49 }, { 47, 60 }, { 48, 50 }, { 48, 61 }, { 49, 51 }, { 49, 62 }, { 50, 63 }, { 51, 64 }, { 52, 55 }, { 52, 62 }, { 52, 65 }, { 53, 56 }, { 53, 63 }, { 53, 66 }, { 54, 57 }, { 54, 64 }, { 54, 67 }, { 55, 58 }, { 55, 68 }, { 56, 59 }, { 56, 69 }, { 57, 60 }, { 57, 70 }, { 58, 61 }, { 58, 71 }, { 59, 62 }, { 59, 72 }, { 60, 63 }, { 60, 73 }, { 61, 64 }, { 61, 74 }, { 62, 75 }, { 63, 76 }, { 64, 77 }, { 65, 71 }, { 65, 72 }, { 66, 72 }, { 66, 73 }, { 67, 73 }, { 67, 74 }, { 68, 74 }, { 68, 75 }, { 69, 75 }, { 69, 76 }, { 70, 76 }, { 70, 77 }, { 71, 77 } });

			// Robertson-Wegner  
			AddGraph(30, 5, 3, new[,] { { 0, 10 }, { 0, 15 }, { 0, 19 }, { 0, 2 }, { 0, 29 }, { 1, 12 }, { 1, 2 }, { 1, 21 }, { 1, 28 }, { 1, 4 }, { 2, 26 }, { 2, 3 }, { 2, 8 }, { 3, 13 }, { 3, 18 }, { 3, 22 }, { 3, 5 }, { 4, 15 }, { 4, 24 }, { 4, 5 }, { 4, 7 }, { 5, 11 }, { 5, 29 }, { 5, 6 }, { 6, 16 }, { 6, 21 }, { 6, 25 }, { 6, 8 }, { 7, 10 }, { 7, 18 }, { 7, 27 }, { 7, 8 }, { 8, 14 }, { 8, 9 }, { 9, 11 }, { 9, 19 }, { 9, 24 }, { 9, 28 }, { 10, 11 }, { 10, 13 }, { 10, 21 }, { 11, 12 }, { 11, 17 }, { 12, 14 }, { 12, 22 }, { 12, 27 }, { 13, 14 }, { 13, 16 }, { 13, 24 }, { 14, 15 }, { 14, 20 }, { 15, 17 }, { 15, 25 }, { 16, 17 }, { 16, 19 }, { 16, 27 }, { 17, 18 }, { 17, 23 }, { 18, 20 }, { 18, 28 }, { 19, 20 }, { 19, 22 }, { 20, 21 }, { 20, 26 }, { 21, 23 }, { 22, 23 }, { 22, 25 }, { 23, 24 }, { 23, 29 }, { 24, 26 }, { 25, 26 }, { 25, 28 }, { 26, 27 }, { 27, 29 }, { 28, 29 } });

			// PP9(1,2,3,4) K4  
			AddGraph(36, 5, 3, new[,] { { 0, 1 }, { 0, 18 }, { 0, 27 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 19 }, { 1, 2 }, { 1, 28 }, { 2, 11 }, { 2, 20 }, { 2, 29 }, { 2, 3 }, { 3, 12 }, { 3, 21 }, { 3, 30 }, { 3, 4 }, { 4, 13 }, { 4, 22 }, { 4, 31 }, { 4, 5 }, { 5, 14 }, { 5, 23 }, { 5, 32 }, { 5, 6 }, { 6, 15 }, { 6, 24 }, { 6, 33 }, { 6, 7 }, { 7, 16 }, { 7, 25 }, { 7, 34 }, { 7, 8 }, { 8, 17 }, { 8, 26 }, { 8, 35 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 9, 27 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 10, 28 }, { 11, 13 }, { 11, 20 }, { 11, 29 }, { 12, 14 }, { 12, 21 }, { 12, 30 }, { 13, 15 }, { 13, 22 }, { 13, 31 }, { 14, 16 }, { 14, 23 }, { 14, 32 }, { 15, 17 }, { 15, 24 }, { 15, 33 }, { 16, 25 }, { 16, 34 }, { 17, 26 }, { 17, 35 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 28, 32 }, { 28, 33 }, { 29, 33 }, { 29, 34 }, { 30, 34 }, { 30, 35 }, { 31, 35 } });

			// PP7(1,2,3,2) C4 × K2  
			AddGraph(56, 5, 4, new[,] { { 0, 1 }, { 0, 21 }, { 0, 28 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 22 }, { 1, 29 }, { 1, 8 }, { 2, 23 }, { 2, 3 }, { 2, 30 }, { 2, 9 }, { 3, 10 }, { 3, 24 }, { 3, 31 }, { 3, 4 }, { 4, 11 }, { 4, 25 }, { 4, 32 }, { 4, 5 }, { 5, 12 }, { 5, 26 }, { 5, 33 }, { 5, 6 }, { 6, 13 }, { 6, 27 }, { 6, 34 }, { 7, 12 }, { 7, 14 }, { 7, 35 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 8, 36 }, { 9, 11 }, { 9, 16 }, { 9, 37 }, { 10, 12 }, { 10, 17 }, { 10, 38 }, { 11, 13 }, { 11, 18 }, { 11, 39 }, { 12, 19 }, { 12, 40 }, { 13, 20 }, { 13, 41 }, { 14, 17 }, { 14, 18 }, { 14, 21 }, { 14, 42 }, { 15, 18 }, { 15, 19 }, { 15, 22 }, { 15, 43 }, { 16, 19 }, { 16, 20 }, { 16, 23 }, { 16, 44 }, { 17, 20 }, { 17, 24 }, { 17, 45 }, { 18, 25 }, { 18, 46 }, { 19, 26 }, { 19, 47 }, { 20, 27 }, { 20, 48 }, { 21, 23 }, { 21, 26 }, { 21, 49 }, { 22, 24 }, { 22, 27 }, { 22, 50 }, { 23, 25 }, { 23, 51 }, { 24, 26 }, { 24, 52 }, { 25, 27 }, { 25, 53 }, { 26, 54 }, { 27, 55 }, { 28, 29 }, { 28, 34 }, { 28, 35 }, { 28, 49 }, { 29, 30 }, { 29, 36 }, { 29, 50 }, { 30, 31 }, { 30, 37 }, { 30, 51 }, { 31, 32 }, { 31, 38 }, { 31, 52 }, { 32, 33 }, { 32, 39 }, { 32, 53 }, { 33, 34 }, { 33, 40 }, { 33, 54 }, { 34, 41 }, { 34, 55 }, { 35, 37 }, { 35, 40 }, { 35, 42 }, { 36, 38 }, { 36, 41 }, { 36, 43 }, { 37, 39 }, { 37, 44 }, { 38, 40 }, { 38, 45 }, { 39, 41 }, { 39, 46 }, { 40, 47 }, { 41, 48 }, { 42, 45 }, { 42, 46 }, { 42, 49 }, { 43, 46 }, { 43, 47 }, { 43, 50 }, { 44, 47 }, { 44, 48 }, { 44, 51 }, { 45, 48 }, { 45, 52 }, { 46, 53 }, { 47, 54 }, { 48, 55 }, { 49, 51 }, { 49, 54 }, { 50, 52 }, { 50, 55 }, { 51, 53 }, { 52, 54 }, { 53, 55 } });

		}

		public static void AddGraph(int n, int deg, int diam, int[,] array)
		{
			AddCase(new Case
			{
				N = n,
				Degree = deg,
				Diameter = diam,
				Action = () =>
				{
					var g = new Graph(n, deg);
					int len = array.GetLength(0);
					for (int i = 0; i < len; i++)
						g.AddBidirectionalEdge(array[i, 0], array[i, 1]);
					return g;
				},
			});
		}

		public static void AddCase(int n, int m, int diam, Func<Graph> action)
		{
			AddCase(new Case
			{
				N= n,
				Degree =m,
				Diameter = diam,
				Action = action,
			});
		}

		public static void AddCase(Case c)
		{
			if (!cases.ContainsKey(c.N))
				cases[c.N] = new List<Case>();
			cases[c.N].Add(c);
		}

		public class Case
		{
			public int N;
			public int Degree;
			public int Diameter;
			public Func<Graph> Action;
		}
		#endregion

		
		public class Graph
		{
			int m;
			int n;
			int version;
			public List<int>[] g;
			
			public Graph(int n, int m)
			{
				this.n = n;
				this.m = m;
				g = new List<int>[n];
				for (int i = 0; i < n; i++)
					g[i] = new List<int>(m);
			}


			public List<int> this[int index] => g[index];

			public static Graph CubeGraph(int m)
			{
				var n = 1 << m;
				var g = new Graph(n, m);

				for(int i=0; i<n; i++)
				{
					for (int j=0; j<m; j++)
						g[i].Add(i ^ (1<<j));
				}
				return g;
			}

			public static Graph RandomGraph(int n, int degree, bool logN)
			{
				var g = CycleGraph(n, degree);

				if (degree == 1) return g;

				// Add second edges
				if (logN)
					g.ReduceDiameterToLogN();

				// Add random edges 
				for (int i = 0; i < n; i++)
				{
					var list = g[i];
					while (list.Count < degree)
					{
						// Excess edges
						if (list.Count >= n - 1)
						{

							list.Add((i + random.Next(1, n)) % n);
							continue;
						}

						int attach = random.Next(0, n - 1 - list.Count);
						int attach2 = attach;
						if (attach >= i) attach2++;
						foreach (var v in list)
							if (attach >= v) attach2++;
						list.Add(attach2);
					}
				}

				return g;
			}


			public int FastDiameter()
			{
				throw new NotImplementedException();
			}

			void ReduceDiameterToLogN()
			{
				int head = 0;
				int[] next = new int[n];

				next[n - 1] = -1;
				for (int i = 0; i+1< n; i++)
					next[i] = i + 1;

				while (head != -1)
				{
					var cur = head;
					var prev = -1;
					int headorig = head;
					while (cur != -1)
					{
						int tmp = cur;
						cur = next[cur]!=-1 ? next[next[cur]] : -1;

						if (prev == -1)
							head = next[tmp];
						else
							next[prev] = next[tmp];

						next[tmp] = cur;
						g[tmp].Add(cur != -1 ? cur : head != -1 && g[tmp].Contains(headorig) ? head : headorig);
					}
				}
			}

			// http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem
			static double MaximumOrderOfGraph(int degree, int diameter)
			{
				// Moore bound
				return (degree * Pow(degree - 1, diameter) - 2) / (degree - 2);

				// Undirected graphs
				// complete graphs on d+1 vertices
				// cycles on 2k+1 vertices (k=diameter)
				// diameter2 - Peterseng graph
				// no moore graphs for K>2 amd d>2
			}

			static double MaximumOrderOfDirectedGraph(int degree, int diameter)
			{
				// Moore bound
				return (Pow(degree, diameter + 1) - 1) / (degree - 1);

				// Directed graphs
				// complete digraphs on d+1 vertices
				// directed cycles on k+1 vertices (k=diameter)
				// no moore graphs for K>1 amd d>1
			}


			// cube n=2^k nodes with both diameter and degree k / in digraph degree might equal 2k
			// connect any two nodes whose index differ in only one digit ( i ^ j ) & (i ^ j) - 1 == 0 

			public int Diameter(int abortBound = int.MaxValue)
			{
				// Could use bitarray
				var visited = new int[g.Length];
				var queue = new Queue<int>();
				int maxDiameter = 0;

				for (int i = 0; i < n; i++)
				{
					Array.Clear(visited, 0, visited.Length);
					queue.Enqueue(i);
					visited[i] = 1;
					while (queue.Count > 0)
					{
						var pop = queue.Dequeue();
						var popdist = visited[pop];
						foreach (var child in g[pop])
						{
							if (visited[child] != 0) continue;
							visited[child] = popdist + 1;
							queue.Enqueue(child);
							if (popdist > maxDiameter)
							{
								maxDiameter = popdist;
								if (maxDiameter >= abortBound)
									return maxDiameter;
							}
						}
					}
				}

				return maxDiameter;
			}

			//http://research.nii.ac.jp/graphgolf/2015/candar15/graphgolf2015-mizuno.pdf


			public void AddBidirectionalEdge(int i, int j)
			{
				if (i == j) return;
				if (!g[i].Contains(j)) g[i].Add(j);
				if (!g[j].Contains(i)) g[j].Add(i);
			}

			public static readonly Graph K2 = Complete(2);

			public static Graph Complete(int n)
			{
				// Degree n-1
				// Diameter 1
				var g = new Graph(n, n - 1);
				for (int i=0; i<n; i++)
					for (int j=i+1; j<n; j++)
						g.AddBidirectionalEdge(i, j);
				return g;
			}

			public static Graph Graph33(int n)
			{
				// Degree and diameter 3
				int[] array = null;
				switch(n)
				{
					case 8:
						array = new[] {6,3,4,1,2,7,0,5};
						break;
					case 10:
						array = new[] {7,6,5,9,8,2,1,0,3,4};
						break;
					case 12:
						array = new[] { 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, 5 };
						break;
					case 14:
						array = new[] { 5, 10, 7, 12, 9, 0, 11,
										2, 13, 4, 1, 6, 3, 8 };
						break;
					case 18:
						array = new[] { 14, 5, 9, 16, 12, 1,
										11, 15, 13, 2, 17, 6,
										4, 8, 0, 7, 3, 10, };
						break;
				}

				if (array == null) return null;
				var g = CycleGraph(n,3,true);
				for (int i = 0; i < array.Length; i++)
					g.AddBidirectionalEdge(i, array[i]);
				return g;
			}

			public static Graph CycleGraph(int n, int m=1, bool bidrectional = false)
			{
				var g = new Graph(n, m);
				g[n - 1].Add(0);
				for (int i = 1; i < n; i++)
					g[i - 1].Add(i);

				if (bidrectional)
				{
					g[0].Add(n-1);
					for (int i = 1; i< n; i++)
						g[i].Add(i-1);
				}
				return g;
			}
            
            public static Graph ConnectedGraph(int n, int m)
			{
				var g = new Graph(n, m);
                
                for (int i=0; i<n; i++)
                   for (int j=0; j<m; j++)
                    {
                        g[i].Add((i*m+j+Extra)%n);
                    }
				return g;
			}

			public static Graph G8(int k)
			{
				// New order = 8 * k
				// New degree = k + 2
				// Diameter = 2

				var g8 = new Graph(8 * k, k + 2);

				for (int i = 0; i < k; i++)
				{
					g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 2);
					g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 3);
					g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 4);
					g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 2);
					g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 3);
					g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 4);
					g8.AddBidirectionalEdge(i * 8 + 2, i * 8 + 5);
					g8.AddBidirectionalEdge(i * 8 + 3, i * 8 + 6);
					g8.AddBidirectionalEdge(i * 8 + 4, i * 8 + 7);
					g8.AddBidirectionalEdge(i * 8 + 5, i * 8 + 6);
					g8.AddBidirectionalEdge(i * 8 + 5, i * 8 + 7);
					g8.AddBidirectionalEdge(i * 8 + 6, i * 8 + 7);
				}

				for (int i=0; i<k; i++)
					for (int j=0; j<k; j++)
					{
						if (i == j) continue;
						g8.AddBidirectionalEdge(i * 8 + 0, j * 8 + 1);
						g8.AddBidirectionalEdge(i * 8 + 1, j * 8 + 0);
						g8.AddBidirectionalEdge(i * 8 + 2, j * 8 + 6);
						g8.AddBidirectionalEdge(i * 8 + 3, j * 8 + 7);
						g8.AddBidirectionalEdge(i * 8 + 4, j * 8 + 5);
						g8.AddBidirectionalEdge(i * 8 + 5, j * 8 + 4);
						g8.AddBidirectionalEdge(i * 8 + 6, j * 8 + 2);
						g8.AddBidirectionalEdge(i * 8 + 7, j * 8 + 3);
					}

				return g8;
			}

			public static Graph Product(Graph g1, Graph g2, bool strong=false)
			{
				var g = new Graph(g1.n * g2.n, g1.m * g2.m + g1.m + g2.m);
				var f = g2.n;

				for (int i = 0; i < g1.n; i++)
				{
					var iedges = g1[i];
					for (int j = 0; j < g2.n; j++)
					{
						var jedges = g2[j];

						foreach (var e1 in iedges)
							g[i * f + j].Add(e1 * f + j);

						foreach (var e2 in jedges)
							g[i * f + j].Add(i * f + e2);

						if (strong)
						{
							foreach (var e1 in iedges)
								foreach (var e2 in jedges)
									g[i * f + j].Add(e1 * f + e2);
						}
					}
				}

				// Preserves diameter
				// Order(g) = Order(g1) * Order(g2)

				// Weak
				// Degree(g) = Degree(g1)+Degree(g2)
				// Diameter(g) = Diameter(g1) + Diameter(g2)

				// Strong
				// if (strong) Degree(g) = Degree(g1)*Degree(g2) + Degree(g1) + Degree(g2)
				// Diameter(g) = Max(Diameter(g1), Diameter(g2))


				// G(n/2,2) * C(2) -> G(n,5)   // C(2) diameter=1
				// G(n/3,2) * C(3) -> G(n/3,5) // C(2) diameter=2 
				// Question: Is C(3) degree 1
				return g;
			}
		}




#if DEBUG
		public static bool Verbose = true;
#else
		public static bool Verbose = false;
#endif
	}

	public class TimestampedArray<T>
	{
		public T[] Array;
		public int[] TimeStamp;
		public int Time;
		public T DefaultValue;

		public TimestampedArray(int size, T defaultValue = default(T))
		{
			Array = new T[size];
			TimeStamp = new int[size];
			DefaultValue = defaultValue;
		}

		public T this[int x]
		{
			get
			{
				return TimeStamp[x] >= Time ? Array[x] : DefaultValue;
			}
			set
			{
				Array[x] = value;
				TimeStamp[x] = Time;
			}
		}

		public bool ContainsKey(int x)
		{
			return TimeStamp[x] >= Time;
		}

		public void InitializeAll()
		{
			for (int i = 0; i < Array.Length; i++)
			{
				if (TimeStamp[i] > Time) continue;
				Array[i] = DefaultValue;
				TimeStamp[i] = Time;
			}
		}

		public void Clear()
		{
			Time++;
		}
	}

	public static class HackerRankUtils
	{

		#region Reporting Answer

		static volatile bool _reported;
		static System.Threading.Timer _timer;
		static Func<bool> _timerAction;

		public static void LaunchTimer(Func<bool> action, long ms = 2800)
		{
			_timerAction = action;
			_timer = new System.Threading.Timer(
				delegate
				{
					Report();
#if !DEBUG
				if (_reported)
					Environment.Exit(0);
#endif
				}, null, ms, 0);
		}

		public static void Report()
		{
			if (_reported) return;
			_reported = true;
			_reported = _timerAction();
		}

		[Conditional("DEBUG")]
		public static void Trace(string s)
		{
			Console.WriteLine(s);
		}

		#endregion


		public static int TimeLimit = 2000;
		public static int RandomIterations = 20;
		public static int RandomIterationsTop = RandomIterations + 20;
        public static int Extra = 1;
	}

Diameter Minimization Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  static Deque<Integer> q = new LinkedList<>();

  static int[] dis = new int[1001];

  static int bfs(int n, int m, int x) {
    Arrays.fill(dis, 1_000_000_000);
    dis[x] = 0;
    q.add(x);
    int mmh = 0;
    while (!q.isEmpty()) {
      int k = q.removeFirst();
      mmh = dis[k];
      for (int i = 0; i < m; i++) {
        int j = (k * m + i) % n;
        if (dis[j] > mmh + 1) {
          dis[j] = mmh + 1;
          q.add(j);
        }
      }
    }
    return mmh;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    dis = new int[n];
    
    int mmh = 0;
    for (int i = 0; i < n; i++) {
      mmh = Math.max(mmh, bfs(n, m, i));
    }
    bw.write(mmh + "\n");
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        bw.write((i * m + j) % n + " ");
      }
      bw.write("\n");
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

Diameter Minimization Python Solution

#!/bin/python3

import sys
import math

def opt_diameter(n, m):
    count = 1
    depth = 0
    while count < n:
        depth += 1
        count = m ** depth
    return depth
    

def diameter(n, m):
    count = 1
    depth = 0
    while count < n:
        depth += 1
        count += m**depth
    left_over = m**depth - (count - n)
    limit = m**(depth - 1)
    discount = 1
    if left_over > limit:
        discount = 0
    return max(depth, 2*depth - discount)

def solve(in_file, out_file):
    n, m = (int(raw) for raw in in_file.readline().strip().split(' '))
    out_file.write("{}\n".format(opt_diameter(n, m)))
    count = 0
    for _ in range(n):
        ret = []
        for _ in range(m):
            val = count % n
            count += 1
            ret.append(str(val))
        out_file.write("{}\n".format(" ".join(ret)))

if __name__ == '__main__':
    from_file = False
    
    if from_file:
        path='Data\\'
        name='mega_prime'
        file_input = open(path+name+'.in', 'r')
        file_output = open(path+name+'.out','w')
        solve(file_input, file_output)
        file_input.close()
        file_output.close()
    else:
        solve(sys.stdin, sys.stdout)
C# C++ HackerRank Solutions java python cppCSharpHackerrank Solutionsjavapython

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes