Guest User

Untitled

a guest
Dec 26th, 2015
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.61 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4.  
  5. public class IzborPredmet {
  6. public static void main(String[] args) throws Exception {
  7. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8. int brojNaPredmeti = Integer.parseInt(br.readLine());
  9. Graph g = new Graph(brojNaPredmeti);
  10. for(int i = 0; i < brojNaPredmeti; ++i) {
  11. String imeNaPredmet = br.readLine();
  12. g.addNode(imeNaPredmet, i);
  13. }
  14. int brojNaZavisniPredmeti = Integer.parseInt(br.readLine());
  15. for(int i = 0; i < brojNaZavisniPredmeti; ++i) {
  16. String predmeti = br.readLine();
  17. String predmet[] = predmeti.split(" ");
  18. for(int j = 1; j < predmet.length; ++j) {
  19. g.addEdge(predmet[0], predmet[j]);
  20. }
  21. }
  22. String poslednoSlushanPredmet = br.readLine();
  23. System.out.println(g.posledenPredmet(poslednoSlushanPredmet));
  24. }
  25. }
  26.  
  27. class Graph {
  28. GraphNode[] jazol;
  29.  
  30. public Graph(int brojNaJazli) {
  31. jazol = new GraphNode[brojNaJazli];
  32. }
  33.  
  34. public void addNode(String imeNaPredmet, int index) {
  35. jazol[index] = new GraphNode(imeNaPredmet, index);
  36. }
  37.  
  38. public void addEdge(String jazol1, String jazol2) {
  39. GraphNode prvJazol = null, vtorJazol = null;
  40. for(GraphNode gn: jazol) {
  41. if(gn.ime.equals(jazol1))
  42. prvJazol = gn;
  43. if(gn.ime.equals(jazol2))
  44. vtorJazol = gn;
  45. }
  46. prvJazol.addNeighbor(vtorJazol);
  47. }
  48.  
  49. public String posledenPredmet(String poslednoSlushanPredmet) {
  50. GraphNode posledenPredmet = null;
  51. for(GraphNode gn: jazol)
  52. if(gn.ime.equals(poslednoSlushanPredmet))
  53. posledenPredmet = gn;
  54. boolean zavrsheni[] = new boolean[jazol.length];
  55. zavrsheniPredmeti(posledenPredmet, zavrsheni);
  56. for(GraphNode gn: jazol) {
  57. if(!zavrsheni[gn.index]&&gn.mozheDaSeSlusha(zavrsheni))
  58. return gn.toString();
  59. }
  60. return "";
  61. }
  62.  
  63. private void zavrsheniPredmeti(GraphNode posledenPredmet, boolean []zavrsheni) {
  64. zavrsheni[posledenPredmet.index] = true;
  65. for(GraphNode gn: posledenPredmet.sosed) {
  66. zavrsheniPredmeti(gn, zavrsheni);
  67. }
  68. }
  69. }
  70.  
  71. class GraphNode {
  72. String ime;
  73. int index;
  74. ArrayList<GraphNode> sosed;
  75.  
  76. public GraphNode(String ime, int index) {
  77. this.ime = ime;
  78. this.index = index;
  79. sosed = new ArrayList<>();
  80. }
  81.  
  82. public boolean containsNeighbor(GraphNode gn) {
  83. return sosed.contains(gn);
  84. }
  85.  
  86. public void addNeighbor(GraphNode gn) {
  87. sosed.add(gn);
  88. }
  89.  
  90. @Override
  91. public String toString() {
  92. return ime;
  93. }
  94.  
  95. public boolean mozheDaSeSlusha(boolean[] zavrsheni) {
  96. for(GraphNode gn: sosed) {
  97. if(!zavrsheni[gn.index])
  98. return false;
  99. }
  100. return true;
  101. }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment