Created
May 3, 2015 20:02
-
-
Save Onaiplee/88cffece94c4e2546c44 to your computer and use it in GitHub Desktop.
Rust & Murderer - Java - alternative
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.util.*; | |
| import java.text.*; | |
| import java.math.*; | |
| import java.util.regex.*; | |
| public class Solution { | |
| public static int INF = Integer.MAX_VALUE >> 2; | |
| public static int int_hash(int key) { | |
| key = ~key + (key << 15); | |
| key = key ^ (key >>> 12); | |
| key = key + (key << 2); | |
| key = key ^ (key >>> 4); | |
| key = key * 2057; | |
| key = key ^ (key >>> 16); | |
| return key; | |
| } | |
| public static class Edge { | |
| private int from; | |
| private int to; | |
| public Edge(final int from, final int to) { | |
| this.from = from; | |
| this.to = to; | |
| } | |
| public boolean equals(Object e) { | |
| Edge edge = (Edge) e; | |
| return (this.from == edge.from && this.to == edge.to); | |
| } | |
| public int hashCode() { | |
| return (51 + int_hash(from)) * 51 + int_hash(to); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Scanner in = new Scanner(System.in); | |
| int t = in.nextInt(); | |
| for (int i = 0; i < t; ++i) { | |
| int N = in.nextInt(); | |
| int M = in.nextInt(); | |
| HashSet<Edge> set = new HashSet<Edge>(); | |
| for (int j = 0; j < M; ++j) { | |
| int from = in.nextInt(); | |
| int to = in.nextInt(); | |
| set.add(new Edge(from, to)); | |
| } | |
| int S = in.nextInt(); | |
| int[] dist = solve(N, M, S, set); | |
| StringBuilder sb = new StringBuilder(); | |
| for (int d = 1; d < dist.length; ++d) { | |
| if (d != S) { | |
| sb.append(Integer.toString(dist[d]) + " "); | |
| } | |
| } | |
| System.out.println(sb.toString()); | |
| } | |
| /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ | |
| } | |
| private static int[] solve(int N, int M, int S, HashSet<Edge> set) { | |
| int[] dist = new int[N+1]; | |
| List<Integer> notVisited = new LinkedList<Integer>(); | |
| for (int i = 1; i <= N; ++i) { | |
| if (i != S) { | |
| notVisited.add(i); | |
| } | |
| } | |
| Queue<Integer> vertices = new LinkedList<Integer>(); | |
| vertices.add(S); | |
| dist[S] = 0; | |
| while (vertices.peek() != null && notVisited.size() != 0) { | |
| int vertex1 = vertices.poll(); | |
| for (Iterator<Integer> iterator = notVisited.iterator(); iterator.hasNext();) { | |
| int vertex2 = iterator.next(); | |
| Edge edge1 = new Edge(vertex1, vertex2); | |
| Edge edge2 = new Edge(vertex2, vertex1); | |
| if (!set.contains(edge1) && !set.contains(edge2)) { | |
| dist[vertex2] = dist[vertex1] + 1; | |
| iterator.remove(); | |
| vertices.add(vertex2); | |
| } | |
| } | |
| } | |
| return dist; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment