Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //import java.util.Iterator;
- import java.util.Stack;
- import java.util.LinkedList;
- import java.util.Scanner;
- 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[];
- boolean visited[];
- @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];
- }
- 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]);
- }
- @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 int getID(String s)
- {
- for(int i = 0 ; i < num_nodes ; ++i)
- if(adjList[i].getInfo().equals(s))
- return i;
- return 0;
- }
- private void dfs(int n)
- {
- //System.out.println(adjList[n].getInfo() + " IS VISITED");
- visited[n] = true;
- LinkedList<GraphNode<E>> ns = adjList[n].getNeighbors();
- for(GraphNode<E> node : ns)
- if(!visited[node.getIndex()])
- dfs(node.getIndex());
- }
- public String solve(String start)
- {
- //System.out.println("STARTING WITH " + start);
- visited = new boolean[num_nodes];
- dfs(getID(start));
- for(int i = 0 ; i < num_nodes ; ++i)
- if(!visited[i])
- {
- //System.out.println("Not visited is " + adjList[i].getInfo());
- boolean flag = true;
- LinkedList<GraphNode<E>> ns = adjList[i].getNeighbors();
- for(GraphNode<E> node : ns)
- if(!visited[node.getIndex()])
- flag = false;
- if(flag)
- return adjList[i].getInfo().toString();
- }
- return null;
- }
- }
- public class IzborPredmet {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int N = in.nextInt();
- Graph<String> graph = new Graph<String>(N);
- for(int i = 0 ; i < N ; ++i)
- graph.adjList[i] = new GraphNode<String>(i, in.next());
- int M = in.nextInt();
- in.nextLine();
- for(int i = 0 ; i < M ; ++i)
- {
- String[] input = in.nextLine().split(" ");
- //System.out.println("Line " + i + " Starting with " + input[0]);
- int toAdd = graph.getID(input[0]);
- for(int j = 1 ; j < input.length ; ++j)
- graph.addEdge(toAdd, graph.getID(input[j]));
- }
- System.out.println(graph.solve(in.nextLine()));
- in.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement