Untying the knot
Let's talk about untying the knot...
You're given a fully-connected, undirected graph that contains at most one knot. A knot is defined as a loop. The graph contains only unique positive integers as the edges, and if an edge (a,b) is in the graph, then it is guaranteed that a!=b. The graph may have up to 10^5 nodes.
In order to untie the knot, you need to first find the loop (if it exists) in the graph, and then find the smallest element in that loop. In the example below, the graph does have one loop, and the smallest element (the weak link) is node 3. That's what you should return. Otherwise, if there is no loop, return -1.
Here is how I solved it:
1/ Created the graph (from the edges) using a hash table (that's my favorite way to handle a graph)
2/ Perform a DFS recursively looking for a loop
3/ As you do the DFS, store the current node and the parent node
4/ Once you find a loop, then backtrack non-recursively in order to find the smallest element
5/ Notice that because the graph is fully connected and undirected, you can start with any node whatsoever, but you also need to ensure that you don't repeat edges in your traversal
Code is down below, cheers, ACC.
using System;
using System.Collections;
using System.Collections.Generic;
namespace UntyingTheKnot
{
public class NodePath
{
public int node = 0;
public NodePath parent = null;
public NodePath(int node, NodePath parent)
{
this.node = node;
this.parent = parent;
}
}
class Program
{
static void Main(string[] args)
{
int[][] edges1 = { new int[] { 1, 2 },
new int[] { 2, 30 },
new int[] { 30, 4 },
new int[] { 30, 5 },
new int[] { 5, 60 },
new int[] { 5, 8 },
new int[] { 8, 14 },
new int[] { 14, 3 },
new int[] { 3, 6 },
new int[] { 6, 9 },
new int[] { 8, 7 },
new int[] { 9, 8 },
new int[] { 9, 10 },
new int[] { 10, 22 },
new int[] { 10, 13 },
new int[] { 13, 11 },
new int[] { 13, 0 }
};
Console.WriteLine(UntieTheKnot(edges1));
int[][] edges2 = { new int[] { 1, 2 },
new int[] { 2, 3 },
new int[] { 3, 1 }
};
Console.WriteLine(UntieTheKnot(edges2));
int[][] edges3 = { new int[] { 1, 2 },
new int[] { 2, 3 },
new int[] { 3, 4 }
};
Console.WriteLine(UntieTheKnot(edges3));
}
static int UntieTheKnot(int[][] edges)
{
//Build the graph (hash table)
Hashtable graph = new Hashtable();
foreach (int[] edge in edges)
{
for (int i = 0; i < 2; i++)
{
if (!graph.ContainsKey(edge[i])) graph.Add(edge[i], new Hashtable());
Hashtable connection = (Hashtable)graph[edge[i]];
if (!connection.ContainsKey(edge[(i + 1) % 2])) connection.Add(edge[(i + 1) % 2], true);
}
}
//We'll pick any node to begin with
//Perform a DFS marking both the node and the edge (BFS does not work!)
//The moment you find a cycle, find the min using backtrack
int retVal = -1;
Stack stack = new Stack();
Hashtable visitedNode = new Hashtable();
Hashtable visitedEdge = new Hashtable();
NodePath nodePath = new NodePath(edges[0][0], null);
UntieTheKnot_Recursive(nodePath,
graph,
visitedNode,
visitedEdge,
ref retVal);
return retVal;
}
static bool UntieTheKnot_Recursive(NodePath currentNode,
Hashtable graph,
Hashtable visitedNode,
Hashtable visitedEdge,
ref int minVal)
{
if (currentNode == null) return false;
if (visitedNode.ContainsKey(currentNode.node))
{
//Find min in the cycle
int endNode = currentNode.node;
Console.WriteLine("Node in knot: {0}", endNode);
NodePath currentNodePath = currentNode.parent;
minVal = Math.Min(currentNodePath.node, endNode);
while (currentNodePath.node != endNode)
{
Console.WriteLine("Node in knot: {0}", currentNodePath.node);
currentNodePath = currentNodePath.parent;
minVal = Math.Min(currentNodePath.node, minVal);
}
return true;
}
visitedNode.Add(currentNode.node, true);
if (graph.ContainsKey(currentNode.node))
{
Hashtable connections = (Hashtable)graph[currentNode.node];
foreach (int connectedNode in connections.Keys)
{
long edgeHash = EdgeUniqueHash(currentNode.node, connectedNode);
if (!visitedEdge.ContainsKey(edgeHash))
{
visitedEdge.Add(edgeHash, true);
NodePath newNodePath = new NodePath(connectedNode, currentNode);
if (UntieTheKnot_Recursive(newNodePath,
graph,
visitedNode,
visitedEdge,
ref minVal)) return true;
}
}
}
return false;
}
static long EdgeUniqueHash(int a, int b)
{
long min = Math.Min(a, b);
long max = Math.Max(a, b);
return min * 10005 + max;
}
}
}
Comments
Post a Comment
[γγ¬γΌγ ]