[APS] Faculty Subjects

import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;
import java.util.LinkedList;

class GraphNode<E> {
    private int index;//index (reden broj) na temeto vo grafot
    private E info;
    private LinkedList<GraphNode<E>> neighbors;

    public GraphNode(int index, E info) {
        this.index = index;
        this.info = info;
        neighbors = new LinkedList<GraphNode<E>>();
    }

    boolean containsNeighbor(GraphNode<E> o){
        return neighbors.contains(o);
    }

    void addNeighbor(GraphNode<E> o){
        neighbors.add(o);
    }


    void removeNeighbor(GraphNode<E> o){
        if(neighbors.contains(o))
            neighbors.remove(o);
    }


    @Override
    public String toString() {
        String ret= "INFO:"+info+" SOSEDI:";
        for(int i=0;i<neighbors.size();i++)
            ret+=neighbors.get(i).info+" ";
        return ret;

    }

    @Override
    public boolean equals(Object obj) {
        @SuppressWarnings("unchecked")
        GraphNode<E> pom = (GraphNode<E>)obj;
        return (pom.info.equals(this.info));
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public E getInfo() {
        return info;
    }

    public void setInfo(E info) {
        this.info = info;
    }

    public LinkedList<GraphNode<E>> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
        this.neighbors = neighbors;
    }



}
class Graph<E> {

    int num_nodes;
    GraphNode<E> adjList[];

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes, E[] list) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            adjList[i] = new GraphNode<E>(i, list[i]);
    }

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            adjList[i] = new GraphNode<E>(i, null);
    }

    int adjacent(int x, int y) {
        // proveruva dali ima vrska od jazelot so
        // indeks x do jazelot so indeks y
        return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
    }

    void addEdge(int x, int y) {
        // dodava vrska od jazelot so indeks x do jazelot so indeks y
        if (!adjList[x].containsNeighbor(adjList[y])) {
            adjList[x].addNeighbor(adjList[y]);
        }
    }

    void deleteEdge(int x, int y) {
        adjList[x].removeNeighbor(adjList[y]);
    }

    /************************TOPOLOGICAL SORT*******************************************************************/

    void dfsVisit(Stack<Integer> s, int i, boolean[] visited){
        if(!visited[i]){
            visited[i] = true;
            Iterator<GraphNode<E>> it = adjList[i].getNeighbors().iterator();
            //System.out.println("dfsVisit: "+i+" Stack="+s);
            while(it.hasNext()){
                dfsVisit(s, it.next().getIndex(), visited);
            }
            s.push(i);
            //System.out.println("--dfsVisit: "+i+" Stack="+s);
        }
    }

    void topological_sort_dfs(int id_predmet){
        boolean visited[] = new boolean[num_nodes];
        for(int i=0;i<num_nodes;i++){
            visited[i] = false;
        }

        Stack<Integer> s = new Stack<Integer>();

        for(int i=0;i<num_nodes;i++){
            dfsVisit(s,i,visited);
        }
        Stack<Integer> new_stack= new Stack<Integer>();
        //System.out.println("----Stack="+s);
        while(!s.isEmpty()){
            //System.out.println(adjList[s.pop()]);
            new_stack.push(s.pop());
        }
        while(new_stack.peek()!=id_predmet) new_stack.pop();
        new_stack.pop();
        if(new_stack.isEmpty()) System.out.println("Ova bese posledniot predmet!");
        else
        System.out.println(this.adjList[new_stack.peek()].getInfo());
    }

    /***********************************************************************************************************/

    @Override
    public String toString() {
        String ret = new String();
        for (int i = 0; i < this.num_nodes; i++)
            ret += i + ": " + adjList[i] + "\n";
        return ret;
    }
    public GraphNode<E> getNode(String ime){
        for(int i=0;i<this.adjList.length;i++){
            if(adjList[i].getInfo().equals(ime)) return adjList[i];
        }
        return null;
    }

}
public class FacultySubjects {
    public static void main(String[] args) {
        Scanner input= new Scanner(System.in);
        int numSubjects= Integer.parseInt(input.nextLine());
        Graph<String> graph= new Graph<>(numSubjects);
        for(int i=0;i<numSubjects;i++){
            String subject_name= input.nextLine();
            graph.adjList[i].setIndex(i);
            graph.adjList[i].setInfo(subject_name);
        }
        int numDependencies= Integer.parseInt(input.nextLine());
        for(int i=0;i<numDependencies;i++){
            String[] dependency= input.nextLine().split("\\s+");
            for(int j=1;j<dependency.length;j++){
                graph.addEdge(graph.getNode(dependency[j]).getIndex(),i);
            }
        }
        String subject= input.nextLine();
        int id_predmet= graph.getNode(subject).getIndex();
        graph.topological_sort_dfs(id_predmet);
    }
}
/*
5
Z1
Z2
I1
I2
I3
3
I1 Z1 Z2
I2 I1
I3 Z2 I2
--------
I2

5
Z1
Z2
I1
I2
I3
3
I1 Z1 Z2
I2 I1
I3 Z2 I2
I3
---------------------------
Ova bese posledniot predmet!
 */