Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Solution {
- public static int[] bfs(List<Integer>[] g, int s) {
- int vertexCount = g.length;
- boolean[] used = new boolean[vertexCount];
- Arrays.fill(used, false);
- int[] p = new int[vertexCount];
- Arrays.fill(p, -1);
- int[] d = new int[vertexCount];
- Arrays.fill(d, Integer.MAX_VALUE);
- Queue<Integer> q = new LinkedList<Integer>();
- p[s] = s;
- d[s] = 0;
- used[s] = true;
- q.add(s);
- while (!q.isEmpty()) {
- int u = q.remove();
- for (int v : g[u]) {
- if (!used[v]) {
- used[v] = true;
- q.add(v);
- d[v] = d[u] + 1;
- p[v] = u;
- }
- }
- }
- return d;
- }
- public static void main(String[] args) throws IOException {
- BufferedReader in = new BufferedReader(new FileReader("input.txt"));
- String[] arr = in.readLine().split(" ");
- int n = Integer.parseInt(arr[0]);
- int m = Integer.parseInt(arr[1]);
- List<Pair> e = new ArrayList<Pair>();
- List<Integer>[] g = new List[n];
- for (int i = 0; i < n; i++) {
- g[i] = new ArrayList<Integer>();
- }
- for (int i = 0; i < m; i++) {
- arr = in.readLine().split(" ");
- int u = Integer.parseInt(arr[0]) - 1;
- int v = Integer.parseInt(arr[1]) - 1;
- g[u].add(v);
- g[v].add(u);
- e.add(new Pair(u, v));
- }
- int[] ds = bfs(g, 0);
- int[] dt = bfs(g, n - 1);
- int[] cnt = new int[n];
- int[] idx = new int[n];
- List<Integer> ans = new ArrayList<Integer>();
- for (int i = 0; i < m; i++) {
- if (ds[e.get(i).u] + 1 + dt[e.get(i).v] == ds[n - 1]) {
- cnt[ds[e.get(i).u]]++;
- idx[ds[e.get(i).u]] = e.get(i).v;
- }
- if (ds[e.get(i).v] + 1 + dt[e.get(i).u] == ds[n - 1]) {
- cnt[ds[e.get(i).v]]++;
- idx[ds[e.get(i).v]] = e.get(i).u;
- }
- }
- for (int i = 0; i < m; i++) {
- if (cnt[ds[e.get(i).u]] == 1 && idx[ds[e.get(i).u]] == e.get(i).v
- || cnt[ds[e.get(i).v]] == 1 && idx[ds[e.get(i).v]] == e.get(i).u) {
- ans.add(i);
- }
- }
- PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
- writer.println(ans.size());
- for (Integer an : ans) {
- writer.print((an + 1) + " ");
- }
- writer.close();
- }
- private static final class Pair {
- private int u;
- private int v;
- private Pair(int u, int v) {
- this.u = u;
- this.v = v;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement