AdventOfCode Day 12 C# faster solution with zero allocations while searching (runs in 25ms on my 8-year-old cpu)

AdventOfCode_Day12_Faster.cs

var input = File.ReadAllText(Path.GetDirectoryName(Util.CurrentQueryPath) + @"\..\Inputs\aoc_day12.txt");
var lines = input.Split('\n').Select(line=>line.Trim()).ToArray();
var connections = new Dictionary<int,List<int>>();
var nodes = new List<string>();

foreach(var line in lines) 
{
	var nodeA = line.Split('-')[0];
	var nodeB = line.Split('-')[1];
	
	if(nodes.IndexOf(nodeA) == -1) nodes.Add(nodeA);
	if(nodes.IndexOf(nodeB) == -1) nodes.Add(nodeB);
	
	int a = nodes.IndexOf(nodeA);
	int b = nodes.IndexOf(nodeB);
	
	if(!connections.TryGetValue(a, out var listA)) connections[a] = listA = new List<int>();
	if(!connections.TryGetValue(b, out var listB)) connections[b] = listB = new List<int>();
	
	listA.Add(b);
	listB.Add(a);
}

var nodeIsUpper = new bool[nodes.Count];
int startIndex = -1;
int endIndex = -1;

for(int n = 0; n<nodes.Count; n++)
{
	var nodeName = nodes[n];
	nodeIsUpper[n] = Char.IsUpper(nodeName[0]);
	
	if(nodeName == "start") startIndex = n;
	if(nodeName == "end") endIndex = n;
}

int numPaths = 0;
var countPerNode = new int[nodes.Count];

DFS(startIndex, false);
	
Console.WriteLine("got count: " + numPaths + " in " + Util.ElapsedTime);

void DFS(int node, bool hasUsedTwice) 
{
	if(node == endIndex) 
	{
		numPaths++;
		return;
	}
	
	if(node == startIndex && countPerNode[startIndex] > 0) return; 
	
	if(!nodeIsUpper[node] && countPerNode[node] > 0)
	{
		if(hasUsedTwice) return;
		else hasUsedTwice = true; 
	}
	
	countPerNode[node]++;
	
	var conns = connections[node];
	int count = conns.Count;
	for(int c = 0; c<count; c++) DFS(conns[c], hasUsedTwice);
	
	countPerNode[node]--;
}