import java.util.*;
import java.lang.*;
import java.io.*;
class AllWalks {
int V;
LinkedList<Integer>[] adj;
boolean[] marked;
public AllWalks(int v) {
this.V = v;
for (int i=0; i<v; i++) {
adj[i] = new LinkedList<Integer>();
}
this.marked = new boolean[v];
}
public void addEdge(int v, int w) {
adj[v].add(w);
}
public void printPossiblePaths(int u, int v, int k, int count, LinkedList<Integer> queue) {
queue.add(u);
marked[u] = true;
Iterator<Integer> iter = adj[u].listIterator();
count++;
while (iter.hasNext()) {
int w = iter.next();
if (!marked[w]) {
if (count==k && w!=v) {
continue;
}
else if (count==k) {
queue.add(w);
//print the stack
for (int j=0;j<queue.size();j++) {
System.
out.
print(queue.
get(j
) + " "); }
//remove the last two elements (unrolling the stack)
queue.removeLast();queue.removeLast();
return;
}
printPossiblePaths(w, v, k, count, queue);
}
marked[u] = false;
}
}
public int printPossiblePathsUsingDP(int u, int v, int k) {
//Create 3D array representing the count of all walks for [ith] vertex to [jth] vertex with exactly [k] edges
int[][][] dpCountArr = new int[V][V][k+1];
boolean flag=false;
for (int e=0;e<k+1;e++) { //Since we want to find the solution for e==k
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
//initialize count to zero
dpCountArr[i][j][e]=0;
//every vertex has a path to itself in zero edges
if (e==0 && i==j) {
dpCountArr[i][j][e]=1;
}
//For all vertices adjacent to i, set count to i if they have a path to vertex j in the given graph
if (e==1) {
//check if a & b are adjacent
Iterator<Integer> iter = adj[i].iterator();
flag=false;
while (iter.hasNext()) {
if (j==iter.next()) {
flag=true;
break;
}
}
if (flag) {
dpCountArr[i][j][e]=1;
}
}
//Start solving for cases with more than one edges
if (e>1) {
//iterate over vertices adjacent to i
Iterator<Integer> iter = adj[i].iterator();
while (iter.hasNext()) {
int w = iter.next();
//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)
dpCountArr[i][j][e]+=dpCountArr[w][j][e-1];
}
}
}
}
}
return dpCountArr[u][v][k];
}
int N = 1;
int u, v, k;
while((N--)!=0) {
int ver = 4;
AllWalks gr = new AllWalks(ver);
String[] strArr
= {"0",
"1",
"1",
"1",
"0",
"0",
"0",
"1",
"0",
"0",
"0",
"1",
"0",
"0",
"0",
"0"}; int vert = 0, edge = 0;
for (int i=0;i<ver*ver;i++) {
vert = i/4;
edge = i%4;
if (strArr[i].equals("1")) {
gr.addEdge(vert, edge);
}
}
u = 0;
v = 3;
k = 2;
LinkedList<Integer> queue = new LinkedList<Integer>();
gr.printPossiblePaths(u, v, k, 0, queue);
System.
out.
println(gr.
printPossiblePathsUsingDP(u, v, k
)); }
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBBbGxXYWxrcyB7CiAgICBpbnQgVjsKICAgIExpbmtlZExpc3Q8SW50ZWdlcj5bXSBhZGo7CiAgICBib29sZWFuW10gbWFya2VkOwoKICAgIHB1YmxpYyBBbGxXYWxrcyhpbnQgdikgewogICAgICAgIHRoaXMuViA9IHY7CiAgICAgICAgdGhpcy5hZGogPSBuZXcgTGlua2VkTGlzdFt2XTsKICAgICAgICBmb3IgKGludCBpPTA7IGk8djsgaSsrKSB7CiAgICAgICAgICAgIGFkaltpXSA9IG5ldyBMaW5rZWRMaXN0PEludGVnZXI+KCk7CiAgICAgICAgfQogICAgICAgIHRoaXMubWFya2VkID0gbmV3IGJvb2xlYW5bdl07CiAgICB9CgogICAgcHVibGljIHZvaWQgYWRkRWRnZShpbnQgdiwgaW50IHcpIHsKICAgICAgICBhZGpbdl0uYWRkKHcpOwogICAgfQoKICAgIHB1YmxpYyB2b2lkIHByaW50UG9zc2libGVQYXRocyhpbnQgdSwgaW50IHYsIGludCBrLCBpbnQgY291bnQsIExpbmtlZExpc3Q8SW50ZWdlcj4gcXVldWUpIHsKICAgICAgICBxdWV1ZS5hZGQodSk7CiAgICAgICAgbWFya2VkW3VdID0gdHJ1ZTsKICAgICAgICBJdGVyYXRvcjxJbnRlZ2VyPiBpdGVyID0gYWRqW3VdLmxpc3RJdGVyYXRvcigpOwogICAgICAgIGNvdW50Kys7CiAgICAgICAgd2hpbGUgKGl0ZXIuaGFzTmV4dCgpKSB7CiAgICAgICAgICAgIGludCB3ID0gaXRlci5uZXh0KCk7CiAgICAgICAgICAgIGlmICghbWFya2VkW3ddKSB7CiAgICAgICAgICAgICAgICBpZiAoY291bnQ9PWsgJiYgdyE9dikgewogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBpZiAoY291bnQ9PWspIHsKICAgICAgICAgICAgICAgICAgICBxdWV1ZS5hZGQodyk7CiAgICAgICAgICAgICAgICAgICAgLy9wcmludCB0aGUgc3RhY2sKICAgICAgICAgICAgICAgICAgICBmb3IgKGludCBqPTA7ajxxdWV1ZS5zaXplKCk7aisrKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQocXVldWUuZ2V0KGopICsgIiAiKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgLy9yZW1vdmUgdGhlIGxhc3QgdHdvIGVsZW1lbnRzICh1bnJvbGxpbmcgdGhlIHN0YWNrKQogICAgICAgICAgICAgICAgICAgIHF1ZXVlLnJlbW92ZUxhc3QoKTtxdWV1ZS5yZW1vdmVMYXN0KCk7CiAgICAgICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludCgiXG4iKTsKICAgICAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBwcmludFBvc3NpYmxlUGF0aHModywgdiwgaywgY291bnQsIHF1ZXVlKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBtYXJrZWRbdV0gPSBmYWxzZTsKICAgICAgICB9CiAgICB9CgogICAgcHVibGljIGludCBwcmludFBvc3NpYmxlUGF0aHNVc2luZ0RQKGludCB1LCBpbnQgdiwgaW50IGspIHsKICAgICAgICAvL0NyZWF0ZSAgM0QgYXJyYXkgcmVwcmVzZW50aW5nIHRoZSBjb3VudCBvZiBhbGwgd2Fsa3MgZm9yIFtpdGhdIHZlcnRleCB0byBbanRoXSB2ZXJ0ZXggd2l0aCBleGFjdGx5IFtrXSBlZGdlcwogICAgICAgIGludFtdW11bXSBkcENvdW50QXJyID0gbmV3IGludFtWXVtWXVtrKzFdOwoKICAgICAgICBib29sZWFuIGZsYWc9ZmFsc2U7CiAgICAgICAgZm9yIChpbnQgZT0wO2U8aysxO2UrKykgeyAgIC8vU2luY2Ugd2Ugd2FudCB0byBmaW5kIHRoZSBzb2x1dGlvbiBmb3IgZT09awogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IFY7IGkrKykgewogICAgICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBWOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICAvL2luaXRpYWxpemUgY291bnQgdG8gemVybwogICAgICAgICAgICAgICAgICAgIGRwQ291bnRBcnJbaV1bal1bZV09MDsKCiAgICAgICAgICAgICAgICAgICAgLy9ldmVyeSB2ZXJ0ZXggaGFzIGEgcGF0aCB0byBpdHNlbGYgaW4gemVybyBlZGdlcwogICAgICAgICAgICAgICAgICAgIGlmIChlPT0wICYmIGk9PWopIHsKICAgICAgICAgICAgICAgICAgICAgICAgZHBDb3VudEFycltpXVtqXVtlXT0xOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAvL0ZvciBhbGwgdmVydGljZXMgYWRqYWNlbnQgdG8gaSwgc2V0IGNvdW50IHRvIGkgaWYgdGhleSBoYXZlIGEgcGF0aCB0byB2ZXJ0ZXggaiBpbiB0aGUgZ2l2ZW4gZ3JhcGgKICAgICAgICAgICAgICAgICAgICBpZiAoZT09MSkgewogICAgICAgICAgICAgICAgICAgICAgICAvL2NoZWNrIGlmIGEgJiBiIGFyZSBhZGphY2VudAogICAgICAgICAgICAgICAgICAgICAgICBJdGVyYXRvcjxJbnRlZ2VyPiBpdGVyID0gYWRqW2ldLml0ZXJhdG9yKCk7CiAgICAgICAgICAgICAgICAgICAgICAgIGZsYWc9ZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgICAgIHdoaWxlIChpdGVyLmhhc05leHQoKSkgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGo9PWl0ZXIubmV4dCgpKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZmxhZz10cnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChmbGFnKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkcENvdW50QXJyW2ldW2pdW2VdPTE7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgIC8vU3RhcnQgc29sdmluZyBmb3IgY2FzZXMgd2l0aCBtb3JlIHRoYW4gb25lIGVkZ2VzCiAgICAgICAgICAgICAgICAgICAgaWYgKGU+MSkgewogICAgICAgICAgICAgICAgICAgICAgICAvL2l0ZXJhdGUgb3ZlciB2ZXJ0aWNlcyBhZGphY2VudCB0byBpCiAgICAgICAgICAgICAgICAgICAgICAgIEl0ZXJhdG9yPEludGVnZXI+IGl0ZXIgPSBhZGpbaV0uaXRlcmF0b3IoKTsKICAgICAgICAgICAgICAgICAgICAgICAgd2hpbGUgKGl0ZXIuaGFzTmV4dCgpKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbnQgdyA9IGl0ZXIubmV4dCgpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9Db3VudCBvZiB3YWxrcyBmcm9tIGktPmogd2l0aCBleGFjdGx5IGUgZWRnZXMgaXMgZXF1YWwgdG8gY291bnQgdG8gd2Fsa3MgZnJvbSB3LT5qIHdpdGggZXhhY3RseSAoZS0xKSBlZGdlcyAod2hlcmUgdyBpcyBhZGphY2VudCB0byBpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgZHBDb3VudEFycltpXVtqXVtlXSs9ZHBDb3VudEFyclt3XVtqXVtlLTFdOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBkcENvdW50QXJyW3VdW3ZdW2tdOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgRXhjZXB0aW9uIHsKCiAgICAgICAgQnVmZmVyZWRSZWFkZXIgYnIgPSBuZXcgQnVmZmVyZWRSZWFkZXIobmV3IElucHV0U3RyZWFtUmVhZGVyKFN5c3RlbS5pbikpOwogICAgICAgIGludCBOID0gMTsKICAgICAgICBpbnQgdSwgdiwgazsKICAgICAgICB3aGlsZSgoTi0tKSE9MCkgewogICAgICAgICAgICBpbnQgdmVyID0gNDsKICAgICAgICAgICAgQWxsV2Fsa3MgZ3IgPSBuZXcgQWxsV2Fsa3ModmVyKTsKICAgICAgICAgICAgU3RyaW5nW10gc3RyQXJyID0geyIwIiwiMSIsIjEiLCIxIiwiMCIsIjAiLCIwIiwiMSIsIjAiLCIwIiwiMCIsIjEiLCIwIiwiMCIsIjAiLCIwIn07CiAgICAgICAgICAgIGludCB2ZXJ0ID0gMCwgZWRnZSA9IDA7CiAgICAgICAgICAgIGZvciAoaW50IGk9MDtpPHZlcip2ZXI7aSsrKSB7CiAgICAgICAgICAgICAgICB2ZXJ0ID0gaS80OwogICAgICAgICAgICAgICAgZWRnZSA9IGklNDsKICAgICAgICAgICAgICAgIGlmIChzdHJBcnJbaV0uZXF1YWxzKCIxIikpIHsKICAgICAgICAgICAgICAgICAgICBnci5hZGRFZGdlKHZlcnQsIGVkZ2UpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIHUgPSAwOwogICAgICAgICAgICB2ID0gMzsKICAgICAgICAgICAgayA9IDI7CgogICAgICAgICAgICBMaW5rZWRMaXN0PEludGVnZXI+IHF1ZXVlID0gbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oKTsKICAgICAgICAgICAgZ3IucHJpbnRQb3NzaWJsZVBhdGhzKHUsIHYsIGssIDAsIHF1ZXVlKTsKCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihnci5wcmludFBvc3NpYmxlUGF0aHNVc2luZ0RQKHUsIHYsIGspKTsKICAgICAgICB9CiAgICB9Cn0=