fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class AllWalks {
  6.     int V;
  7.     LinkedList<Integer>[] adj;
  8.     boolean[] marked;
  9.  
  10.     public AllWalks(int v) {
  11.         this.V = v;
  12.         this.adj = new LinkedList[v];
  13.         for (int i=0; i<v; i++) {
  14.             adj[i] = new LinkedList<Integer>();
  15.         }
  16.         this.marked = new boolean[v];
  17.     }
  18.  
  19.     public void addEdge(int v, int w) {
  20.         adj[v].add(w);
  21.     }
  22.  
  23.     public void printPossiblePaths(int u, int v, int k, int count, LinkedList<Integer> queue) {
  24.         queue.add(u);
  25.         marked[u] = true;
  26.         Iterator<Integer> iter = adj[u].listIterator();
  27.         count++;
  28.         while (iter.hasNext()) {
  29.             int w = iter.next();
  30.             if (!marked[w]) {
  31.                 if (count==k && w!=v) {
  32.                     continue;
  33.                 }
  34.                 else if (count==k) {
  35.                     queue.add(w);
  36.                     //print the stack
  37.                     for (int j=0;j<queue.size();j++) {
  38.                         System.out.print(queue.get(j) + " ");
  39.                     }
  40.                     //remove the last two elements (unrolling the stack)
  41.                     queue.removeLast();queue.removeLast();
  42.                     System.out.print("\n");
  43.                     return;
  44.                 }
  45.                 printPossiblePaths(w, v, k, count, queue);
  46.             }
  47.             marked[u] = false;
  48.         }
  49.     }
  50.  
  51.     public int printPossiblePathsUsingDP(int u, int v, int k) {
  52.         //Create  3D array representing the count of all walks for [ith] vertex to [jth] vertex with exactly [k] edges
  53.         int[][][] dpCountArr = new int[V][V][k+1];
  54.  
  55.         boolean flag=false;
  56.         for (int e=0;e<k+1;e++) {   //Since we want to find the solution for e==k
  57.             for (int i = 0; i < V; i++) {
  58.                 for (int j = 0; j < V; j++) {
  59.                     //initialize count to zero
  60.                     dpCountArr[i][j][e]=0;
  61.  
  62.                     //every vertex has a path to itself in zero edges
  63.                     if (e==0 && i==j) {
  64.                         dpCountArr[i][j][e]=1;
  65.                     }
  66.                     //For all vertices adjacent to i, set count to i if they have a path to vertex j in the given graph
  67.                     if (e==1) {
  68.                         //check if a & b are adjacent
  69.                         Iterator<Integer> iter = adj[i].iterator();
  70.                         flag=false;
  71.                         while (iter.hasNext()) {
  72.                             if (j==iter.next()) {
  73.                                 flag=true;
  74.                                 break;
  75.                             }
  76.                         }
  77.                         if (flag) {
  78.                             dpCountArr[i][j][e]=1;
  79.                         }
  80.                     }
  81.  
  82.                     //Start solving for cases with more than one edges
  83.                     if (e>1) {
  84.                         //iterate over vertices adjacent to i
  85.                         Iterator<Integer> iter = adj[i].iterator();
  86.                         while (iter.hasNext()) {
  87.                             int w = iter.next();
  88.                             //Count of walks from i->j with exactly e edges is equal to count to walks from w->j with exactly (e-1) edges (where w is adjacent to i)
  89.                             dpCountArr[i][j][e]+=dpCountArr[w][j][e-1];
  90.                         }
  91.                     }
  92.                 }
  93.             }
  94.         }
  95.         return dpCountArr[u][v][k];
  96.     }
  97.  
  98.     public static void main (String[] args) throws Exception {
  99.  
  100.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  101.         int N = 1;
  102.         int u, v, k;
  103.         while((N--)!=0) {
  104.             int ver = 4;
  105.             AllWalks gr = new AllWalks(ver);
  106.             String[] strArr = {"0","1","1","1","0","0","0","1","0","0","0","1","0","0","0","0"};
  107.             int vert = 0, edge = 0;
  108.             for (int i=0;i<ver*ver;i++) {
  109.                 vert = i/4;
  110.                 edge = i%4;
  111.                 if (strArr[i].equals("1")) {
  112.                     gr.addEdge(vert, edge);
  113.                 }
  114.             }
  115.             u = 0;
  116.             v = 3;
  117.             k = 2;
  118.  
  119.             LinkedList<Integer> queue = new LinkedList<Integer>();
  120.             gr.printPossiblePaths(u, v, k, 0, queue);
  121.  
  122.             System.out.println(gr.printPossiblePathsUsingDP(u, v, k));
  123.         }
  124.     }
  125. }
Success #stdin #stdout 0.09s 320512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 3 
0 2 3 
2
https://ideone.com/xK3EYf
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!