Hospital.java

import java.util.*;
class Hospital {
    private int V; // number of vertices in the graph (number of rooms in the hospital)
    private ArticPointDFS AdjList; // the graph (the hospital)
    private Vector<Integer> RatingScore; // the weight of each vertex (rating score of each room)
    class Vertex {
        int id, low, dfsnum, dfslevel, numChildren;
        Vertex parent;
        LinkedList<Integer> eList;  // list of edges incident to this vertex
        // Create a vertex with given ID number
        Vertex(int x) {
            parent = null;
            id = x;
            dfsnum = -1;  // initially undiscovered
            eList = new LinkedList<Integer>();  // create empty list for adjacency edges
        }
    }
    class Edge {
        Vertex from, to;   // two vertices incident to this edge
        // Create an edge with given vertices
        Edge(Vertex a, Vertex b) {
            from = a;  to = b;
        }
        // Return the string repesent'n of the edge in form of a pair of vertices
        String getEdge() {
            return "("+from.id+","+to.id+")";
        }
        // Check if two edges are the same by comparing two vertices in edges
        boolean equal(Vertex a, Vertex b) {
            return ((from.id == a.id) && (to.id == b.id));
        }
    }

    public class ArticPointDFS {
        private Vertex[] vArray; // an array which represents a graph
        private int numVertices; // total number of vertices in a graph
        private int dfsCounter = 1;  // will be used to assign dfsNum to each vertex
        private ArrayList<Vertex> articPointList;
        Vertex dfsRoot;
        int rootChildren;
        public ArticPointDFS(int n) {
            numVertices = n;
            // Create an array to set up all vertices in a graph
            vArray = new Vertex[numVertices];
            for(int i=0; i < numVertices; i++) {
                vArray[i] = new Vertex(i);
            }
            articPointList = new ArrayList<Vertex>();
        }
        public void addEdge(int from, int to) {
            Vertex v1 = vArray[from];
            Vertex v2 = vArray[to];
            if (v1.eList.contains(v2)){
                return;
            }
            // Add the edge to the adjacent edge list of both vertices
            v1.eList.add(to);
            v2.eList.add(from);
        }
        public void doArticPointDFS(Vertex vertex) {
            // Set DFS info of vertex 'vertex'
            vertex.dfsnum = dfsCounter++;
            //System.out.println(vertex.id + " " + vertex.dfsnum);
            vertex.low = vertex.dfsnum;
            Iterator<Integer> neighbourIter = vertex.eList.iterator();
            while(neighbourIter.hasNext()) {
                int idxNeighbour = neighbourIter.next();
                Vertex neighbour = vArray[idxNeighbour];
                if (neighbour.dfsnum == -1) {  // this neighbour is undiscovered
                    neighbour.parent = vertex;
                    neighbour.dfslevel = vertex.dfslevel + 1;
                    vertex.numChildren++;
                    doArticPointDFS(neighbour);  // recursively perform DFS at children nodes
                    if (vertex.dfsnum == 1) {
                        // Special Case for root
                        // Root is an artic. point iff there are two or more children
                        if (vertex.numChildren >=2) {
                            if (!articPointList.contains(vertex)) {
                                articPointList.add(vertex);
                            }
                        }
                    }
                    else{
                        if (neighbour.low >= vertex.dfsnum) {
                            // v is artic. point seperating x. That is, children of v
                            // cannot climb higher than v without passing through v.
                            if (!articPointList.contains(vertex)) {
                                articPointList.add(vertex);
                            }
                        }
                    }
                    vertex.low = Math.min(vertex.low, neighbour.low);
                }
                //else if (neighbour.dfslevel < vertex.dfslevel - 1) {
                else if (neighbour != vertex.parent){
                    // x is at a lower level than the level of v's parent.
                    // equiv. (v,x) is a back edge
                    vertex.low = Math.min(vertex.low, neighbour.dfsnum);
                }
            }
        }
    }
    int Query() {
        int answer = -1;

        //Vertex startVertex = AdjList.vArray[0];
        //AdjList.doArticPointDFS(startVertex);  // Perform aritc. point search
        if (AdjList.articPointList.isEmpty()) {
            return answer;
        }
        else {
            Iterator<Vertex> iter1 = AdjList.articPointList.iterator();
            while (iter1.hasNext()) {
                Vertex v = iter1.next();
                if ((answer == -1) || ((answer != -1) && (answer > RatingScore.elementAt(v.id)))){
                    answer = RatingScore.elementAt(v.id);;
                }
            }
        }
        return answer;
    }
    void run() {
        // do not alter this method
        Scanner sc = new Scanner(System.in);
        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 List
            AdjList = new ArticPointDFS(V);
            for (int i = 0; i < V; i++) {
                int k = sc.nextInt(); //number of edges from node i
                while (k-- > 0) {
                    int j = sc.nextInt(); //destination
                    AdjList.addEdge(i,j);
                }
            }
            Vertex[] vertexArray = AdjList.vArray;

            for (int o = 0; o < vertexArray.length; o++){
                if (vertexArray[o].dfsnum == -1){
                    AdjList.doArticPointDFS(vertexArray[o]);
                }
            }
            System.out.println(Query());
        }

    }
    public static void main(String[] args) {
        // do not alter this method
        Hospital ps3 = new Hospital();
        ps3.run();
    }
}