finding all the paths is crazy)) in worst case you get about n! paths.
But even having all the paths, it is not clear how you can find out if
there are k of them sharing no vertex. It is sort of set covering
problem that is not very easy by itself.
Java solution:
public static String f(String s) {
int len = s.length();
if (len 3) return null;
int[] buf = new int[256*256*256];
int cur = (s.charAt(0) 8) | s.charAt(1);
++buf[cur];
for (int i = 0;
Java solution:
public static String f(String s) {
int len = s.length();
if (len 3) return null;
int[] buf = new int[256*256*256];
int cur = (s.charAt(0) 8) | s.charAt(1);
for (int i = 2; i len; ++i)
Java solution:
public static String f(String s) {
int len = s.length();
if (len 3) return null;
int[] buf = new int[256*256*256];
int cur = (s.charAt(0) 8) | s.charAt(1);
for (int i = 2; i len; ++i)
hard to undestand what you mean by removing vertices in the path and
not
edges. How can you remove a vertex without removing all its edges ?
When i talked of maximum flow i of course ment that you also need put
restriction on vertexes too. All edges and vertexes have unit capacity.
there is an example of BFS fail:
- - - 2 6 - - - -- 7- - - - -
S / -- - - - - - /F
- - - 3- - - - 4 - -- - - 5 - -- - - -
going form S to F. k = 2. BFS finds path S37F, as it is shortest.
After removing this path there is no other path from S to F. But
You could use binary heap, so the compexity is O(n log k) and you get
the final list immediatly.
First you put into heap first elements of the streams. Than you repeat
the following step:
extract minimal element from heap, add it to output stream and add next
element from the stream to which