CareerCup

from collections import defaultdict

class AdjNode:
	def __init__(self, vertex, weight):
		self.v = vertex
		self.weight = weight
	
	def get_v(self):
		return self.v
		
	def get_weight(self):
		return self.weight
		
class Graph:
	def __init__(self, vertices):
		self.graph = defaultdict(list)
		self.V = vertices
		
	def add_edge(self, u, v, weight):
		node = AdjNode(v, weight)
		self.graph[u].append(node)
		
	def topological_sort_util(self, v, visited, stack):
		visited[v] = 1
		for vert in self.graph[v]:
			node = vert
			if not visited[node.get_v()]:
				self.topological_sort_util(node.get_v(), visited, stack)
		
		stack.insert(0, v)

	def topological_sort(self):
		stack = []
		visited = [0] * self.V
		for i in range(self.V):
			if not visited[i]:
				self.topological_sort_util(i, visited, stack)
		return stack
	
	def longest_path(self, source):
		dist = [-float('inf') if i is not source else 0 for i in range(self.V)]
		top_sort = self.topological_sort()
		while top_sort:
			u = top_sort.pop(0)
			if dist[u] != -(float('inf')):
				for i in self.graph[u]:
					if dist[i.get_v()] < (dist[u] + i.get_weight()):
						dist[i.get_v()] = dist[u] + i.get_weight()
		print max(dist)	
		
g = Graph(6)
g.add_edge(5, 0, 1)
g.add_edge(5, 2, 1)
g.add_edge(4, 0, 1)
g.add_edge(4, 1, 1)
g.add_edge(3, 1, 1)
g.add_edge(2, 3, 1)
g.longest_path(3)

public static int maxDistance(final Node node, final int currentMax, int max) {
if ((node.getLeftNode() == null) && (node.getRightNode() == null)) {
if (currentMax > max) {
max = currentMax;
}
} else {
if (node.getLeftNode() != null) {
max = maxDistance(node.getLeftNode(), currentMax + 1, max);
} else if (node.getRightNode() != null) {
max = maxDistance(node.getRightNode(), currentMax + 1, max);
}
}
return max;
}

public static int maxDistance(final Node node, final int currentMax, int max) {
        if ((node.getLeftNode() == null) && (node.getRightNode() == null)) {
            if (currentMax > max) {
                max = currentMax;
            }
        } else {
            if (node.getLeftNode() != null) {
                max = maxDistance(node.getLeftNode(), currentMax + 1, max);
            } else if (node.getRightNode() != null) {
                max = maxDistance(node.getRightNode(), currentMax + 1, max);
            }
        }
        return max;
    }

public static int maxDistance(final Node node, final int currentMax, int max) {
        if ((node.getLeftNode() == null) && (node.getRightNode() == null)) {
            if (currentMax > max) {
                max = currentMax;
            }
        } else {
            if (node.getLeftNode() != null) {
                max = maxDistance(node.getLeftNode(), currentMax + 1, max);
            } else if (node.getRightNode() != null) {
                max = maxDistance(node.getRightNode(), currentMax + 1, max);
            }
        }
        return max;
    }

can we flip dijkstra's algorithm instead of calculating single source shortest path, we can find single source longest path using max heap instead of min heap?