Advertisement
add1ctus

Untitled

Dec 27th, 2015
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.13 KB | None | 0 0
  1. //import java.util.Iterator;
  2. import java.util.Stack;
  3. import java.util.LinkedList;
  4. import java.util.Scanner;
  5.  
  6. class GraphNode<E> {
  7.     private int index;//index (reden broj) na temeto vo grafot
  8.     private E info;
  9.     private LinkedList<GraphNode<E>> neighbors;
  10.    
  11.     public GraphNode(int index, E info) {
  12.         this.index = index;
  13.         this.info = info;
  14.         neighbors = new LinkedList<GraphNode<E>>();
  15.     }
  16.    
  17.     boolean containsNeighbor(GraphNode<E> o){
  18.         return neighbors.contains(o);
  19.     }
  20.    
  21.     void addNeighbor(GraphNode<E> o){
  22.         neighbors.add(o);
  23.     }
  24.    
  25.     void removeNeighbor(GraphNode<E> o){
  26.         if(neighbors.contains(o))
  27.             neighbors.remove(o);
  28.     }
  29.    
  30.     @Override
  31.     public String toString() {
  32.         String ret= "INFO:"+info+" SOSEDI:";
  33.         for(int i=0;i<neighbors.size();i++)
  34.         ret+=neighbors.get(i).info+" ";
  35.         return ret;
  36.        
  37.     }
  38.  
  39.     @Override
  40.     public boolean equals(Object obj) {
  41.         @SuppressWarnings("unchecked")
  42.         GraphNode<E> pom = (GraphNode<E>)obj;
  43.         return (pom.info.equals(this.info));
  44.     }
  45.  
  46.     public int getIndex() {
  47.         return index;
  48.     }
  49.  
  50.     public void setIndex(int index) {
  51.         this.index = index;
  52.     }
  53.  
  54.     public E getInfo() {
  55.         return info;
  56.     }
  57.  
  58.     public void setInfo(E info) {
  59.         this.info = info;
  60.     }
  61.  
  62.     public LinkedList<GraphNode<E>> getNeighbors() {
  63.         return neighbors;
  64.     }
  65.  
  66.     public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
  67.         this.neighbors = neighbors;
  68.     }
  69. }
  70.  
  71.  
  72. class Graph<E> {
  73.  
  74.     int num_nodes;
  75.     GraphNode<E> adjList[];
  76.     boolean visited[];
  77.  
  78.     @SuppressWarnings("unchecked")
  79.     public Graph(int num_nodes, E[] list) {
  80.         this.num_nodes = num_nodes;
  81.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  82.         for (int i = 0; i < num_nodes; i++)
  83.             adjList[i] = new GraphNode<E>(i, list[i]);
  84.     }
  85.  
  86.     @SuppressWarnings("unchecked")
  87.     public Graph(int num_nodes) {
  88.         this.num_nodes = num_nodes;
  89.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  90.     }
  91.  
  92.     int adjacent(int x, int y) {
  93.         // proveruva dali ima vrska od jazelot so
  94.         // indeks x do jazelot so indeks y
  95.         return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  96.     }
  97.  
  98.     void addEdge(int x, int y) {
  99.         // dodava vrska od jazelot so indeks x do jazelot so indeks y
  100.         if (!adjList[x].containsNeighbor(adjList[y])) {
  101.             adjList[x].addNeighbor(adjList[y]);
  102.         }
  103.     }
  104.  
  105.     void deleteEdge(int x, int y) {
  106.         adjList[x].removeNeighbor(adjList[y]);
  107.     }
  108.  
  109.     @Override
  110.     public String toString() {
  111.         String ret = new String();
  112.         for (int i = 0; i < this.num_nodes; i++)
  113.             ret += i + ": " + adjList[i] + "\n";
  114.         return ret;
  115.     }
  116.  
  117.     public int getID(String s)
  118.     {
  119.         for(int i = 0 ; i < num_nodes ; ++i)
  120.             if(adjList[i].getInfo().equals(s))
  121.                 return i;
  122.         return 0;
  123.     }
  124.    
  125.     private void dfs(int n)
  126.     {
  127.         //System.out.println(adjList[n].getInfo() + " IS VISITED");
  128.         visited[n] = true;
  129.         LinkedList<GraphNode<E>> ns = adjList[n].getNeighbors();
  130.         for(GraphNode<E> node : ns)
  131.             if(!visited[node.getIndex()])
  132.                 dfs(node.getIndex());
  133.     }
  134.    
  135.     public String solve(String start)
  136.     {
  137.         //System.out.println("STARTING WITH " + start);
  138.         visited = new boolean[num_nodes];
  139.         dfs(getID(start));
  140.         for(int i = 0 ; i < num_nodes ; ++i)
  141.             if(!visited[i])
  142.             {
  143.                 //System.out.println("Not visited is " + adjList[i].getInfo());
  144.                 boolean flag = true;
  145.                 LinkedList<GraphNode<E>> ns = adjList[i].getNeighbors();
  146.                 for(GraphNode<E> node : ns)
  147.                     if(!visited[node.getIndex()])
  148.                         flag = false;
  149.                 if(flag)
  150.                     return adjList[i].getInfo().toString();
  151.             }
  152.         return null;
  153.     }
  154.    
  155. }
  156.  
  157. public class IzborPredmet {
  158.     public static void main(String[] args) {
  159.         Scanner in = new Scanner(System.in);
  160.        
  161.         int N = in.nextInt();
  162.        
  163.         Graph<String> graph = new Graph<String>(N);
  164.        
  165.         for(int i = 0 ; i < N ; ++i)
  166.             graph.adjList[i] = new GraphNode<String>(i, in.next());
  167.        
  168.         int M = in.nextInt();
  169.         in.nextLine();
  170.        
  171.         for(int i = 0 ; i < M ; ++i)
  172.         {
  173.             String[] input = in.nextLine().split(" ");
  174.             //System.out.println("Line " + i + " Starting with " + input[0]);
  175.             int toAdd = graph.getID(input[0]);
  176.  
  177.             for(int j = 1 ; j < input.length ; ++j)
  178.                 graph.addEdge(toAdd, graph.getID(input[j]));
  179.         }
  180.        
  181.         System.out.println(graph.solve(in.nextLine()));
  182.        
  183.         in.close();
  184.     }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement