106 lines
2.1 KiB
Java
106 lines
2.1 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.HashMap;
|
|
import java.util.LinkedList;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.Queue;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
|
|
public class Timus1651 {
|
|
public void solve2(int testNumber, InputReader in, OutputWriter out) {
|
|
int n = in.nextInt();
|
|
int[] a = in.nextIntArray(n);
|
|
|
|
int[] best = new int[100000];
|
|
int[] from = new int[100000];
|
|
|
|
Arrays.fill(best, Integer.MAX_VALUE);
|
|
best[a[0]] = 0;
|
|
from[a[0]] = 0;
|
|
|
|
for (int i = 1; i < n; i++) {
|
|
int t = a[i];
|
|
int p = a[i - 1];
|
|
if (best[t] > best[p] + 1) {
|
|
best[t] = best[p] + 1;
|
|
from[t] = i;
|
|
}
|
|
}
|
|
|
|
LinkedList<Integer> result = new LinkedList<>();
|
|
|
|
for (int c = n - 1; c >= 0;) {
|
|
int t = a[c];
|
|
result.addFirst(t);
|
|
c = from[t] - 1;
|
|
}
|
|
|
|
for (int i : result) {
|
|
out.print(i + " ");
|
|
}
|
|
}
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
int n = in.nextInt();
|
|
int[] a = in.nextIntArray(n);
|
|
|
|
int M = 100100;
|
|
|
|
List<List<Integer>> edges = new ArrayList<>();
|
|
|
|
for (int i = 0; i < M; i++) {
|
|
edges.add(new ArrayList<>());
|
|
}
|
|
|
|
for (int i = 1; i < n; i++) {
|
|
int t = a[i];
|
|
int p = a[i - 1];
|
|
edges.get(p).add(t);
|
|
}
|
|
|
|
int start = a[0];
|
|
int finish = a[n - 1];
|
|
|
|
int[] dist = new int[M];
|
|
Arrays.fill(dist, Integer.MAX_VALUE);
|
|
dist[start] = 0;
|
|
|
|
int[] from = new int[M];
|
|
from[start] = -1;
|
|
|
|
List<Integer> vertices = new ArrayList<>();
|
|
vertices.add(a[0]);
|
|
while (!vertices.isEmpty()) {
|
|
List<Integer> newVertices = new ArrayList<>();
|
|
|
|
for (int i : vertices) {
|
|
for (int j : edges.get(i)) {
|
|
if (dist[j] == Integer.MAX_VALUE) {
|
|
dist[j] = dist[i] + 1;
|
|
from[j] = i;
|
|
newVertices.add(j);
|
|
}
|
|
}
|
|
}
|
|
|
|
vertices = newVertices;
|
|
}
|
|
|
|
LinkedList<Integer> result = new LinkedList<>();
|
|
|
|
for (int t = finish; t >= 0;) {
|
|
result.addFirst(t);
|
|
t = from[t];
|
|
}
|
|
|
|
for (int i : result) {
|
|
out.print(i + " ");
|
|
}
|
|
}
|
|
}
|