Skip to content

Instantly share code, notes, and snippets.

@jiewmeng
Created September 25, 2012 01:29
Show Gist options
  • Save jiewmeng/3779445 to your computer and use it in GitHub Desktop.
Save jiewmeng/3779445 to your computer and use it in GitHub Desktop.
Data Structures & Algorithms - Lab 3
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment