CareerCup

It's O(1). Use a magic potion if needed to turn the enemy link into a friend link, and go directly from the start node to the end node. Neat trick question.

O(E * log(V)) using Dijkstra Algorithm.

It is a union-find problem. Balanced tree implementation takes O(lg N).

Here is the sketch of the solution which runs in O(E).
Let's call friend edges white and enemy edges black.
First we need to find all the connected components of the graph with white edges. We can run simple dfs or bfs for that. Now let's assume that a connected component in one vertex. And let's build new graph on this set of new vertices. The edges of this graph are black edges (more specifically if we have four vertices and white edges 1-2, 3,4 and black edges 2-3,1-2,1-4, we will first find that there are 2 components (1,2) and (3,4) and then the edge in the new graph will connect these 2 components). On the new graph we need the shortest path and check if it costs less than k.

Second solution, also O(E). We will use 0-1-bfs: bfs on the graph with edges of weights 0 and 1. You can read more about it in the net. Here we just use it to find the shortest path and check it to be less than k.

“every two nodes are either friends or enemies with each other”
There for, for any 2 nodes they are either friends or enemies.
If the two you need to get between are friends you are done
If they are enemies use your magic potion.
Obviously there is something else going on here.
Perhaps it should be reworded to state that some nodes are connected to other nodes via friend links and others are connected using enemies and some nodes are not directly connected to other nodes. I suppose you might also stipulate that all the nodes are indirectly linked in one way or another.
Then your task is to find a path from one node to another minimizing the number of enemy links you must traverse. Or perhaps the goal is to find the path that only uses a certain number of enemy links.
Or perhaps they are all interlinked and maybe the goal is to travel through all of the other nodes expending a minimum amount of potion though the first interpretation seems far more likely.

Its a Shortest Path Problem
Assign Friend edges length 0 and enemy edges length 1
find the shortest path and whenever you encounter enemy edge increase answer by 1

my algo:

if(next node is a fried){
travel and add in stack
}

if(next node is enemy){
pop and go to previos friend node an calth the next path if there are more paths, else keep on poping to its previois fiend nodes)

eventually if there exists a path it will be found......


conplexity(worst case is n square)
best is (n log n)