| 32 | |
| 33 | // query key 0 return length; 1 return id |
| 34 | private void findSAP(int v, int w) { |
| 35 | if (v < 0 || v >= g.V() || w < 0 || w >= g.V()) throw new IllegalArgumentException(); |
| 36 | if (v == w) { |
| 37 | length = 0; |
| 38 | ancestor = w; |
| 39 | return; |
| 40 | } |
| 41 | int[] dist1 = new int[g.V()]; |
| 42 | int[] dist2 = new int[g.V()]; |
| 43 | Arrays.fill(dist1, -1); |
| 44 | Arrays.fill(dist2, -1); |
| 45 | // run BFS from v, log every ancestor's distance to v |
| 46 | Queue<Integer> todo = new Queue<>(); |
| 47 | todo.enqueue(v); |
| 48 | dist1[v] = 0; |
| 49 | while (!todo.isEmpty()) { |
| 50 | int p = todo.dequeue(); |
| 51 | for (int q : g.adj(p)) { |
| 52 | if (dist1[q] < 0) { // unmarked (unvisited) |
| 53 | dist1[q] = dist1[p] + 1; |
| 54 | todo.enqueue(q); |
| 55 | } |
| 56 | } |
| 57 | } |
| 58 | int min = Integer.MAX_VALUE; |
| 59 | // run BFS from w |
| 60 | dist2[w] = 0; |
| 61 | todo.enqueue(w); |
| 62 | while (!todo.isEmpty()) { |
| 63 | int p = todo.dequeue(); |
| 64 | // find result, dist1[q] >= 0 means first BFS visited |
| 65 | if (dist1[p] >= 0 && dist1[p] + dist2[p] < min) { |
| 66 | min = dist1[p] + dist2[p]; |
| 67 | ancestor = p; |
| 68 | } |
| 69 | for (int q : g.adj(p)) { |
| 70 | if (dist2[q] < 0) { // unmarked (unvisited) |
| 71 | dist2[q] = dist2[p] + 1; |
| 72 | todo.enqueue(q); |
| 73 | } |
| 74 | } |
| 75 | } |
| 76 | if (ancestor == -1) length = -1; |
| 77 | else length = min; |
| 78 | } |
| 79 | |
| 80 | private void findSAP(Iterable<Integer> v, Iterable<Integer> w) { |
| 81 | int[] dist1 = new int[g.V()]; |