CareerCup

This can be solved as a Spanning Tree. The concept is keeps checking and removing spanning trees from the graph until a loop is found or no nodes left

public bool hasCycle(List<String, String> input)
{
	HashSet<String> nodes = new HashSet<String>(input.keySet());
	List<String> spanning = new LinkedList<String>();
	
	while(nodes.size()>0)
	{
		spanning.add(nodes.get(0));
		int expanded = 0;
		while(expanded < spanning.size())
		{
			String parent = spanning.get(expanded++);
			if(!input.containsKey(parent))
				continue;
			String son = input.get(parent);
			if(spanning.contains(son))
				return false;
			spanning.add(son);
		}			
		nodes.removeAll(spanning);
		spanning.clear();
	}
	return true;
}

Looking for a better solution.

Use a hashmap to store the visited nodes as traversing down. if the hashmap contains the key, we have a cycle.