Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- public class IzborPredmet {
- public static void main(String[] args) throws Exception {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- int brojNaPredmeti = Integer.parseInt(br.readLine());
- Graph g = new Graph(brojNaPredmeti);
- for(int i = 0; i < brojNaPredmeti; ++i) {
- String imeNaPredmet = br.readLine();
- g.addNode(imeNaPredmet, i);
- }
- int brojNaZavisniPredmeti = Integer.parseInt(br.readLine());
- for(int i = 0; i < brojNaZavisniPredmeti; ++i) {
- String predmeti = br.readLine();
- String predmet[] = predmeti.split(" ");
- for(int j = 1; j < predmet.length; ++j) {
- g.addEdge(predmet[0], predmet[j]);
- }
- }
- String poslednoSlushanPredmet = br.readLine();
- System.out.println(g.posledenPredmet(poslednoSlushanPredmet));
- }
- }
- class Graph {
- GraphNode[] jazol;
- public Graph(int brojNaJazli) {
- jazol = new GraphNode[brojNaJazli];
- }
- public void addNode(String imeNaPredmet, int index) {
- jazol[index] = new GraphNode(imeNaPredmet, index);
- }
- public void addEdge(String jazol1, String jazol2) {
- GraphNode prvJazol = null, vtorJazol = null;
- for(GraphNode gn: jazol) {
- if(gn.ime.equals(jazol1))
- prvJazol = gn;
- if(gn.ime.equals(jazol2))
- vtorJazol = gn;
- }
- prvJazol.addNeighbor(vtorJazol);
- }
- public String posledenPredmet(String poslednoSlushanPredmet) {
- GraphNode posledenPredmet = null;
- for(GraphNode gn: jazol)
- if(gn.ime.equals(poslednoSlushanPredmet))
- posledenPredmet = gn;
- boolean zavrsheni[] = new boolean[jazol.length];
- zavrsheniPredmeti(posledenPredmet, zavrsheni);
- for(GraphNode gn: jazol) {
- if(!zavrsheni[gn.index]&&gn.mozheDaSeSlusha(zavrsheni))
- return gn.toString();
- }
- return "";
- }
- private void zavrsheniPredmeti(GraphNode posledenPredmet, boolean []zavrsheni) {
- zavrsheni[posledenPredmet.index] = true;
- for(GraphNode gn: posledenPredmet.sosed) {
- zavrsheniPredmeti(gn, zavrsheni);
- }
- }
- }
- class GraphNode {
- String ime;
- int index;
- ArrayList<GraphNode> sosed;
- public GraphNode(String ime, int index) {
- this.ime = ime;
- this.index = index;
- sosed = new ArrayList<>();
- }
- public boolean containsNeighbor(GraphNode gn) {
- return sosed.contains(gn);
- }
- public void addNeighbor(GraphNode gn) {
- sosed.add(gn);
- }
- @Override
- public String toString() {
- return ime;
- }
- public boolean mozheDaSeSlusha(boolean[] zavrsheni) {
- for(GraphNode gn: sosed) {
- if(!zavrsheni[gn.index])
- return false;
- }
- return true;
- }
- }
Add Comment
Please, Sign In to add comment