Find a cycle of a given length in a graph

graphCycles.cs

void Main()
{
	var n0 = new Node<string>("n0", null);
	var n1 = new Node<string>("n1", null);
	var n2 = new Node<string>("n2", null);
	var n3 = new Node<string>("n3", null);
	var n4 = new Node<string>("n4", null);
	var n5 = new Node<string>("n5", null);
	var n6 = new Node<string>("n6", null);
	var n7 = new Node<string>("n7", null);
	var n8 = new Node<string>("n8", null);


	// 8-shaped
//		n1.setNodes(new Node<string>[] { n2 });
//		n2.setNodes(new Node<string>[] { n3, n5 });
//		n3.setNodes(new Node<string>[] { n4 });
//		n4.setNodes(new Node<string>[] { n1 });
//		n5.setNodes(new Node<string>[] { n6 });
//		n6.setNodes(new Node<string>[] { n1 });


	// something simple
	//	n1.setNodes(new Node[] { n2 });
	//	n2.setNodes(new Node[] { n3, n4 });
	//	n3.setNodes(new Node[] { n4 });
	//	n4.setNodes(new Node[] { n1, n2 });

	// https://activities.tjhsst.edu/sct/lectures/1516/SCT_Tarjans_Algorithm.pdf
	//n0.setNodes(new Node<string>[] { n0 });
		n1.setNodes(new Node<string>[] { n2 });
		n2.setNodes(new Node<string>[] { n3, n5, n6, n7 });
	
		n4.setNodes(new Node<string>[] { n7 });
		n5.setNodes(new Node<string>[] { n1 });
		n6.setNodes(new Node<string>[] { n2, n7 });
		n7.setNodes(new Node<string>[] { n3, n4 });
		n8.setNodes(new Node<string>[] { n4 });

	var graph = new Node<string>[] {n0, n1, n2, n3, n4, n5, n6, n7, n8};
	
	Aux.readInput();
	
	graph.hasCycleOfLength(8).Dump();
	

//	n1.DFS(_ => _.Select(n => n.name).Dump("@1"));//.Dump("DFS starting at n1");
//	n2.DFS(_ => _.Select(n => n.name).Dump("@2"));//.Dump("DFS starting at n2");
//	n3.DFS(_ => _.Select(n => n.name).Dump("@3"));//.Dump("DFS starting at n2");
//	n4.DFS(_ => _.Select(n => n.name).Dump("@4"));//.Dump("DFS starting at n2");


//	n2.DFS().Dump("DFS starting at n2");
//	n3.DFS().Dump("DFS starting at n3");
//	n4.DFS().Dump("DFS starting at n4");
//	n5.DFS().Dump("DFS starting at n4");
//	n4.DFS().Dump("DFS starting at n4");
//	n4.DFS().Dump("DFS starting at n4");
	
//	graph.hasCycleOfLength(3).Dump("graph.hasCycleOfLength(3)");
}

delegate void CycleDetected<T>(IEnumerable<Node<T>> cycle);

class Node<T>
{
	public string name { get; set; }
	public List<Node<T>> nodes { get; set; }

	public void setNodes(IEnumerable<Node<T>> ns)
	{
		nodes = new List<Node<T>>();
		
		if (null == ns)
		{
			return;
		}

		nodes.AddRange(ns);
	}

	public Node(string name, IEnumerable<Node<T>> ns)
	{
		this.name = name;
		this.setNodes(ns);
	}
	
}


static class Aux
{
	class ListIntersectComparer : IEqualityComparer<List<string>>
	{
		public bool Equals(List<string> x, List<string> y)
		{
			return x.Intersect(y).Any();
		}

		public int GetHashCode(List<string> obj) => 7;
	}

	public class MyStringListComparer : IEqualityComparer<List<string>>
	{
		public bool Equals(List<string> x, List<string> y)
		{			
			return x.Zip(y, (_x, _y) => _x == _y).All(_ => _);
		}

		public int GetHashCode(List<string> obj) => 7;
	}


	public static bool hasCycleOfLength<T>(this Node<T>[] graph, int m)
	{
		var allCycles = new HashSet<List<string>>(new MyStringListComparer());
		foreach (var n in graph)
		{
			n.DFS(cyc =>
			{
				allCycles
				.Add(cyc.Select(_ => _.name)
						.OrderBy(_ => _)
						.ToList()
						);
			});
		}

		allCycles.Dump("Unique cycles");

		if (allCycles.Any(_ => 1 == _.Count()))
		{
			// cycle of 1 - we can do anything!
			return true;
		}
		
		// otherwise check if the diophantine equation has a solution
		// but first - need to group the connected cycles
		var connectedCycles = allCycles
			.GroupBy(_=>_, new ListIntersectComparer())
			.Select(_=>_.Select(__=>__.Count()).Distinct())
			.Dump("Connected cycles' lengths")
			;

		// UF: need to make sure we have a positive solution?
		if (!connectedCycles.Select(_ => 0 == m % gcd(_)).Any(_ => _))
		{
			return false;
		}
		
		foreach (var cc in connectedCycles)
		{
			if (findAllPositiveSolutions(cc, m).Any())
			{
				return true;
			}
		}
		
		return false;
	}


	static IEnumerable<int> findAllPositiveSolutions(IEnumerable<int> ks, int c)
	{
		if (ks.Count() < 2)
		{
			if (0 == c % ks.First())
			{
				yield return c / ks.First();
			}

			yield break;
		}

		foreach (var x0 in Enumerable.Range(0, c / ks.First()))
		{
			var tail = findAllPositiveSolutions(ks.Skip(1), c - x0 * ks.First()).ToList();

			if (tail.Any())
			{
				yield return x0;
				foreach (var t in tail)
				{
					yield return t;
				}
			}
		}
	}

	static int gcd(IEnumerable<int> bs)
	{
		if (1 < bs.Count())
		{
			return gcd(bs.First(), bs.Skip(1));
		}

		return bs.First();
	}

	static int gcd(int a, IEnumerable<int> bs)
	{
		if (bs.Count() < 2)
		{
			return gcd(a, bs.First());
		}

		return gcd(gcd(a, bs.First()), bs.Skip(1));
	}

	static int gcd(int a, int b)
	{
		return (a % b == 0) ? Math.Abs(b) : gcd(b, a % b);
	}



	public static IEnumerable<Node<T>> DFS<T>(this Node<T> start, CycleDetected<T> cd)
	{
		var res = new Stack<Node<T>>();
		DFS_helper(start, res, cd);
		
		return res;
	}

	static void DFS_helper<T>(Node<T> start, Stack<Node<T>> found, CycleDetected<T> cd)
	{
		if (found.Any()
		&& found.Last().name == start.name)
		{
			cd(found.Reverse());
			return;
		}

		if (found.Any(_ => _.name == start.name))
		{
			return;
		}

		found.Push(start);
		
		foreach (var n in start.nodes)
		{
			DFS_helper(n, found, cd);
		}
		
		found.Pop();
	}

	public static void readInput()
	{
		var matrix = new List<string>();
		var graph = new List<Node<string>>();

		foreach (var i in Enumerable.Range(0, Int16.Parse(Console.ReadLine())))
		{
			matrix.Add(Console.ReadLine());
			graph.Add(new Node<string>($"{graph.Count()}", null));
		}

		foreach (var l in Enumerable.Range(0, matrix.Count()))
		{
			matrix[l]
				.ToCharArray()
				.Select((_, i) =>
			{
				if ('1' == _)
				{
					graph[l].nodes.Add(graph[i]);
				}

				return true;
			}
			).Count();
		}

		var m = Int16.Parse(Console.ReadLine());
	}
}