NP HARD Problem Longest Path in Graph I got stuck with this problem since the whole day.
When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading selecting the maximum of the edge weight or the alternate path from the other vertex.

So, we are able to solve this problem because of topological sorting which can be done only for acyclic graphs. Thus this type of question can be solved only for acyclic graph.
Now, if I present another case. What if all the edge have the same weight and we don't look in the cycle of the graph. Is this solvable. Everytime I think about this I don't see any use of topological sorting if we can choose any source considering we have to choose the maximum number of nodes(longest path).
Is this also NP Hard or can we solve this?

If you're looking for a longest simple path (with each node appearing at most once) in an arbitrary directed weighted graph, then this is NP-hard, as shown by an easy reduction from the (undirected) Traveling Salesman Problem.
(Details left to the OP such as not to do his homework for him).
