CareerCup

public static void printPaths(int mat[][], int s, int t, int n,ArrayList<Integer> list) {
		
		if (list.contains(new Integer(t + ""))) {
			System.out.println(list);
			return;
		}
		
		for (int i = 0; i < n; i++) {
			if (mat[s][i] == 1) {
				list.add(new Integer(i));
				mat[s][i] = 0;
				mat[i][s]=0;
				printPaths(mat, i, t, n, list);
				list.remove((Object) i);
				mat[s][i] = 1;
				mat[i][s]=1;
			}
		}
	}

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int n = new Integer(s);
		int mat[][] = new int[n][n];

		for (int i = 0; i < n; i++) {
			s = br.readLine();
			String arr[] = s.split(" ");
			for (int j = 0; j < n; j++)
				mat[i][j] = new Integer(arr[j]);
		}
		Integer s1=1,t1=0;
		ArrayList list=new ArrayList<Integer>();
		list.add(s1);
		printPaths(mat, s1, t1, n, list);
	}

* code performs DFS and checks for all possible paths between s and t .
* mat is the sqaure matrix of size n*n.
* list in recursion maintains all the paths

think of Binary Tree kind of structure. where 'a' will be the root. 'b' and 'c' can be right and left nodes of it. and 'd' can be child of both...but i am not sure if this leads to the right answer...any thoughts ???

We can use a adjacency matrix for this. Now whichever nodes we have traversed we can mark them as done so that we do not visit them again

C++ code:
DFS, marks nodes as visited when going in, unvisited when going out, stops at destination node and outputs path.

#include <string>
#include <list>
#include <iostream>

class Node;
class Node
{
public:
    std::string name;
    std::list<Node*> adjacent; // list of adjacent nodes
    bool visited;
};

void search_path ( Node& node, Node& destination, std::string path )
{
    if ( node.visited )
        return;
    
    if ( &node == &destination )
    {
        std::cout << path + node.name << std::endl;
        return;
    }
    
    node.visited = true;
    
    std::string path_so_far = path + node.name + "--";
    
    for ( std::list<Node*>::iterator iter = node.adjacent.begin(); iter!=node.adjacent.end(); iter++ )
    {
        search_path ( **iter, destination, path_so_far );
    }
    
    node.visited = false;
}

int main()
{
    //Construct nodes and connect them + initialize their member "visited" to false; 
    //....
   
    search_path(node1,node2,"");
    
    return 0;
}