Data Structures & Algorithms - Lab 3

HospitalTour.java

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();
  }
}