Advertisement
Guest User

Untitled

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