public
Created

Data Structures & Algorithms - Lab 3

  • Download Gist
HospitalTour.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
import java.util.*;
 
// A0087884H
// Lim Jiew Meng
// Collaborators:
 
class HospitalTour {
private int V; // number of vertices in the graph (number of rooms in the hospital)
private ArrayList<HashSet<Integer>> AdjList; // the graph (the hospital)
private Vector < Integer > RatingScore; // the weight of each vertex (rating score of each room)
 
private boolean[] visited;
 
public HospitalTour() {
}
 
int Query() {
int answer = Integer.MAX_VALUE;
boolean areConnectedComponents;
HashSet<Integer> neighbours;
 
// for each node
for (int i = 0; i < V; i++) {
// loop through its neighbours
neighbours = new HashSet<Integer>(AdjList.get(i)); // a clone to avoid concurrent modification exception
for (int neighbour : neighbours) {
// try disconnecting vertices
disconnect(i, neighbour);
 
// if the nodes are connected components, test if they can still connect to each other
// Assumption: they can connect to each other before
areConnectedComponents = isConnectedComponent(i) && isConnectedComponent(neighbour);
if (areConnectedComponents && !isConnected(i, neighbour)) {
// update answer as applicable
if (RatingScore.get(i) < answer) {
answer = RatingScore.get(i);
}
if (RatingScore.get(neighbour) < answer) {
answer = RatingScore.get(neighbour);
}
}
 
// reconnect the vertices
connect(i, neighbour);
}
}
return (answer == Integer.MAX_VALUE) ? -1 : answer;
}
 
// Assumption: a undirected graph
void connect(int node1, int node2) { // O(1)
AdjList.get(node1).add(node2);
AdjList.get(node2).add(node1);
}
 
void disconnect(int node1, int node2) { // O(1)
AdjList.get(node1).remove(node2);
AdjList.get(node2).remove(node1);
}
 
boolean isConnected(int node1, int node2) {
visited = new boolean[V];
return _isConnected(node1, node2);
}
 
boolean _isConnected(int node1, int node2) {
visited[node1] = true;
if (node1 == node2) {
return true;
} else {
for (int neighbour : AdjList.get(node1)) {
if (!visited[neighbour]) {
if (_isConnected(neighbour, node2)) {
return true;
}
}
}
}
return false;
}
 
boolean isConnectedComponent(int node) {
return AdjList.get(node).size() > 0;
}
 
 
// --------------------------------------------
 
void run() {
// do not alter this method
Scanner sc = new Scanner(System.in);
HashSet<Integer> neighbours;
 
int TC = sc.nextInt(); // there will be several test cases
while (TC-- > 0) {
V = sc.nextInt();
 
// read rating scores, A (index 0), B (index 1), C (index 2), ..., until the V-th index
RatingScore = new Vector < Integer > ();
for (int i = 0; i < V; i++)
RatingScore.add(sc.nextInt());
 
// clear the graph and read in a new graph as Adjacency Matrix
AdjList = new ArrayList<HashSet<Integer>>(V);
for (int i = 0; i < V; i++) {
neighbours = new HashSet<Integer>();
int k = sc.nextInt();
while (k-- > 0) {
int j = sc.nextInt();
neighbours.add(j); // edge weight is always 1 (the weight is on vertices now)
}
AdjList.add(neighbours);
}
 
System.out.println(Query());
}
}
 
public static void main(String[] args) {
// do not alter this method
HospitalTour ps3 = new HospitalTour();
ps3.run();
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.