TwiNNeR

javaaps

Dec 26th, 2015
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
Add Comment
Please, Sign In to add comment