CareerCup

import java.util.*;

/*
 * The core concept is to record and break the circle for each one you found.
 */
public class LgstCircleProblem {
	public static void main(String[] args) {
		Node a = new Node(1, "a");
		Node b = new Node(2, "b");
		Node c = new Node(3, "c");
		Node d = new Node(4, "d");
		Node e = new Node(5, "e");
		Node f = new Node(6, "f");
		Node g = new Node(7, "g");
		Node h = new Node(8, "h");
		Node i = new Node(9, "i");
		List<Node> aList = new ArrayList<Node>();
		aList.add(b);
		aList.add(c);
		aList.add(d);
		a.connected = aList;
		List<Node> bList = new ArrayList<Node>();
		bList.add(e);
		bList.add(a);
		b.connected = bList;
		List<Node> cList = new ArrayList<Node>();
		cList.add(a);
		cList.add(f);
		c.connected = cList;
		List<Node> dList = new ArrayList<Node>();
		dList.add(a);
		dList.add(e);
		dList.add(i);
		d.connected = dList;
		List<Node> eList = new ArrayList<Node>();
		eList.add(b);
		eList.add(d);
		eList.add(f);
		e.connected = eList;
		List<Node> fList = new ArrayList<Node>();
		fList.add(c);
		fList.add(e);
		fList.add(g);
		f.connected = fList;
		List<Node> gList = new ArrayList<Node>();
		gList.add(f);
		gList.add(h);
		g.connected = gList;
		List<Node> hList = new ArrayList<Node>();
		hList.add(g);
		hList.add(i);
		h.connected = hList;
		List<Node> iList = new ArrayList<Node>();
		iList.add(h);
		iList.add(d);
		i.connected = iList;
		List<Node> graph = new ArrayList<Node>();
		graph.add(a);
		graph.add(b);
		graph.add(c);
		graph.add(d);
		graph.add(e);
		graph.add(f);
		graph.add(h);
		graph.add(i);
		findlgstCircle(graph);
	}

	public static void findlgstCircle(List<Node> graph) {
		// for each node in graph, find the longest path with that node and the
		// remaining node.
		Set<Integer> markOut = new HashSet<Integer>();
		Circle circle = null;
		for (Node n : graph) {
			Circle newCircle = findlgstCircleWithN(n, n.connected, markOut);
			if(newCircle!=null ){
				newCircle.nodes.add(n);
				if (circle == null || newCircle.getLength() > circle.getLength()) {
					circle = newCircle;
				}
			}
			markOut.add(n.index);
		}
		System.out.println("length: " + circle == null ? 0 : circle.getLength());
		System.out.println(circle);
	}

	public static Circle findlgstCircleWithN(Node n, List<Node> connected,
			Set<Integer> markOut) {
		// for each neighbor not marked out, find the circle with
		Circle circle = null;
		if (n.connected != null) {
			for (Node x : n.connected) {
				// break a & x, then find a max way to get back to a from x
				removeLink(n, x);
				Set<Integer> markOut4X = new HashSet<Integer>();
				Circle circleX = findMaxCircleXToN(x, n, markOut4X);
				if (circleX != null) {
					if (circle == null
							|| circleX.getLength() > circle.getLength()) {
						circle = circleX;
					}
				}
			}
		}
		return circle;
	}

	public static Circle findMaxCircleXToN(Node x, Node n,
			Set<Integer> markOut4X) {
		Circle circleX = null;
		List<Node> connected = x.connected;
		markOut4X.add(x.index);
		if (connected != null && !connected.isEmpty()) {
			for (Node y : connected) {
				if (!markOut4X.contains(y.index) && !(x.breakLinks!= null && x.breakLinks.contains(y.index))) {
					Circle circle = null;
					if (y.index == n.index) {
						// break the end of the circle so it's not visited again.
						removeLink(x, n);
						circle = new Circle();
						circle.nodes = new ArrayList<Node>();
						circle.nodes.add(n);
						circle.nodes.add(x);
						if (circle != null) {
							if (circleX == null || circleX.getLength() < circle.getLength()) {
								circleX = circle;
							}
						}
					}else {
						markOut4X.add(y.index);
						circle = findMaxCircleXToN(y, n, markOut4X);
						if (circle != null) {
							circle.nodes.add(x);
						}
					}
					if (circle != null) {
						if (circleX == null || circleX.getLength() < circle.getLength()) {
							circleX = circle;
						}
	
					}
				}
			}
		}
		return circleX;
	}

	public static void removeLink(Node n, Node x) {
		Set<Integer> breakLinks = n.breakLinks;
		if(breakLinks == null){
			breakLinks = new HashSet<Integer>();
		}
		breakLinks.add(x.index);
		n.breakLinks = breakLinks;
		breakLinks = x.breakLinks;
		if(breakLinks == null){
			breakLinks = new HashSet<Integer>();
		}
		breakLinks.add(n.index);
		x.breakLinks = breakLinks;
	}

}

class Circle {
	List<Node> nodes;
	Circle() {
	}

	int getLength() {
		return nodes.size() > 0 ? nodes.size() : 0;
	}
	@Override
	public String toString(){
		StringBuilder sb = new StringBuilder();
		if(nodes!=null && !nodes.isEmpty()) {
			sb.append(nodes.get(0).name);
			for(int i=1; i< nodes.size(); i++){
				sb.append("->" + nodes.get(i).name);
			}
		}
		return sb.toString();
	}
}

class Node {
	List<Node> connected;
	Set<Integer> breakLinks;
	String name;
	int index;

	Node(int index, String name) {
		this.index = index;
		this.name = name;
	}
}

Do not try to solve it - it would be at best an useless exercise.
Here we go :
[ stackoverflow.com/questions/4530120/finding-the-longest-cycle-in-a-directed-graph-using-dfs ]
It is NP complete.

Why is it NP?

You can mark edges as negative and find min-route by using Floyd(O(N^3)) or Ford-Bellman(O(N*M)) algorithm.

@rganeyev
e.g. because Floyd-Warshall doesn't work with negative cycles as bellmann ford doesn't
an intuitive prove of this is that if you walk through the negative cycle once more, you will get an even "longer" path with the words of the question or a even "shorter path" in terms of the original algorithms.

Further, it has been shown that the problem can be deduced to a known NP complete problem.

but anyway, I don't agree it's a useless exercise, sometimes even an exponential algo is okay as long as you know it is exponential and if you can roughly prove it's in NP in an interview, I suppose some companies would love you ;-)

def findLongestCycle(root):

	longest_cycle = []
	dfs_stack = [root]
	cycle_stack = [root]

	while (dfs_stack):
		# DFS
		node = dfs_stack.pop()
		node.visited = True
		# This boolean checks whether a node's neighbors have been fully explored
		found_unvisited = False
		for neighbor in node.neighbors:
			if (!neighbor.visited):
				# Add node to our stacks to explore
				dfs_stack.append(neighbor)
				cycle_stack.append(neighbor)
				found_unvisited = True
			else:
				# Dismiss "cycle" if it's just two nodes connected to each other
				if (neighbor != cycle_stack[-2]):
					# Cycle found
					# Compare with current longest cycle
					# Search current_stack to find index of this visited node
					for i, possibility in enumerate(current_stack):
						if possibility == neighbor:
							length = len(cycle_stack) - (i + 1)
							if (length > len(longest_cycle)):
								longest_cycle = cycle_stack[i:]
		if (!found_unvisited):
			# This node has been fully explored
			cycle_stack.pop()

	return longest_cycle

Even if it is NP complete, that only means there's no clever algorithm to solve it, but solving it correctly the naive way can still be a worthwhile exercise.

def findLongestCycle(root):

	longest_cycle = []
	dfs_stack = [root]
	cycle_stack = [root]

	while (dfs_stack):
		# DFS
		node = dfs_stack.pop()
		node.visited = True
		# This boolean checks whether a node's neighbors have been fully explored
		found_unvisited = False
		for neighbor in node.neighbors:
			if (!neighbor.visited):
				# Add node to our stacks to explore
				dfs_stack.append(neighbor)
				cycle_stack.append(neighbor)
				found_unvisited = True
			else:
				# Dismiss "cycle" if it's just two nodes connected to each other
				if (neighbor != cycle_stack[-2]):
					# Cycle found
					# Compare with current longest cycle
					# Search current_stack to find index of this visited node
					for i, possibility in enumerate(current_stack):
						if possibility == neighbor:
							length = len(cycle_stack) - (i + 1)
							if (length > len(longest_cycle)):
								longest_cycle = cycle_stack[i:]
		if (!found_unvisited):
			# This node has been fully explored
			cycle_stack.pop()

	return longest_cycle