CareerCup

It's an undirected graph, so paths dont matter. You could go to a far away node, come back to the source and then go to the destination. The only thing that matters is if the two nodes are in the same connected component (if they are not you should return -1 or something of a sort). Otherwise pick all of source neighbours, and there neighbours etc and put them into a set, if the node is already in the set, then you dont need to go to it heighbours again. When you are done, if destination is in the set, just count the nodes in the set (which you could have done on your way to building the set) and possibly substract 2, in case you don't want to consider the source and destination

Since we need to consider all the simple paths, I propose the following algorithm:
Do a normal dfs(or bfs) rooted at the src node. We keep a visited array to track that we do not run into loops. When we have found the destination at some point in the traversal, we return from that search branch. At the end of the recursive call, we mark the node as un-visited, so that we can explore other paths which may emerge from this node. Also to track the uniqueness of the nodes visited, we add all the nodes on a particular path in a set(set have the property of storing only unique elements).
I think that we can do better in space complexity.
Sample code is as follows, I've tested it for small inputs:

// A private member of Graph class 
set <int> uniqueVisited;

// Method of Class
void Graph::AddPath(int l) {
     for(int i = 0; i < l; ++i) {
         cout << path[i] << " ";
         uniqueVisited.insert(path[i]);
     }
     cout << endl;
}

void Graph::getAllPaths(int s, int dest, int level) {
    path[level] = s;

    if (s == dest) {
        AddPath(level + 1);
        return;
    }

    visited[s] = true;
    list <int> :: iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i) {
        if(!dekha[*i])
            getAllPaths(*i, dest, level + 1);
    }
    visited[s] = false;

}
// Method to print the set
void Graph::printSet()
{
    set<int>::iterator it;
    cout << "Set is";
    for (it = uniqueVisited.begin(); it != uniqueVisited.end(); ++it)
        cout << " " << *it;
    cout << endl;
}

Since you didn't say "simple path" we must consider a loop off of any simple path from src to dest and count the vertices in the loop too. And if such a loop exists, there are infinite paths from src to dest. So take care to make sure any algorithms that correctly add the vertices of such a loop doesn't run forever...

:)

That is to say your "considering all paths" should not be literally translated to "must traverse all paths."

practically... we cannot use loops... as it will only add to complexity... also.. in computr netwrx... if u keep visiting a group of hops again and again... it will send back an icmp packet... so may be it is obvious to rule out the possibility of loops... now.. for each node.. we first mpodify the structure to contain a boolean flag.. which we will turn on visiting each node... so thus.. it will tell us if we have entered some loop or not... then.. we can use the recursive function... to generate all posiible paths...

Here is part of a class that could solve the problem. The key is to DFS and recurse on any nodes not in your current path while looking for the destination node.

HashSet<String> mConnectedNodes;
    Stack<String> stack;


    public void findNodesOnAllConnectingPaths(Node startNode, Node endNode) {
        stack.push(startNode.getValue());

        // Check for the base case = finding destination node on path
        if (startNode.getValue() == endNode.getValue()) {
            Enumeration<String> currentElements = stack.elements();
            while(currentElements.hasMoreElements()) {
                mConnectedNodes.add(currentElements.nextElement());
            }
            stack.pop();
            return;
        }

        //Recurse if any connected nodes aren't on the current path
        ArrayList<Node> nodes = startNode.getConnectedNodes();
        for (Node node : nodes) {
            if (!stack.contains(node.getValue())) {
                findNodesOnAllConnectingPaths(node, endNode);
            }
        }
        stack.pop();
        return;
    }

static int CountDistinctNodesFromSourceToDestination(List<int>[] graph, int n, int source, int dest)
{
    bool[] inPath = new bool[n];

    DFS(source, dest, graph, new bool[n], inPath);

    return inPath.Where(_ => _).Count();
}

static bool DFS(int v, int dest, List<int>[] g, bool[] used, bool[] inPath)
{
    bool pathFound = false;
    if (v == dest)
    {
        pathFound = true;
    }
    else
    {
        used[v] = true;

        foreach (int u in g[v])
        {
            if (!used[u])
            {
                pathFound |= DFS(u, dest, g, used, inPath);
            }
        }

        used[v] = false;
    }

    inPath[v] |= pathFound;

    return pathFound;
}

is it allowed to visit to visit a node more than 1 time in different paths?

how many paths are there in the following graph: ideone.com /YD2KMm ?
src = 0, dst = 6

- do a normal dfs from the source
- once you reach destination node, mark all nodes on the path as being connected to the destination
- now while exploring other paths, if you ever hit a node that has a path to destination, then mark all nodes on the current path as connected to destination and return

- to keep track of nodes connected to destination, we can simply keep connected nodes in a hash set

I propose a recursive solution using memoization. You start DFS from the source, visiting all the nodes till you meet destination. If you can reach a destination from a given node, then you add it to the sum, otherwise you don't. Please see the following pseudo code.

int findAllNodes(Node * curNode)
{
	// don't consider already visited nodes
	if(curNode.pathSize)
		return pathSize;
	// if node is a destination, return that your reached destination
	if(curNode == destination)
		return 1;
	int sum = 0;
	// consider all the neigbours of a given node and count different nodes
	for(int i = 0; i < curNode.neighours.size(); i++)
		sum += findAllNodes(curNode.neighbours[i]);
	curNode->pathSize = sum ? sum + 1 : 0;
	return curNode->pathSize;
}