bizzcuit

Cheaters

Feb 13th, 2019
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.40 KB | None | 0 0
  1. package com.company;
  2.  
  3. import java.io.ByteArrayInputStream;
  4. import java.util.*;
  5.  
  6. public class Cheaters {
  7. private static Set<String> visited = new HashSet<>();
  8. private static List<String> result = new ArrayList<>();
  9. private static Map<String, Map<String, List<String>>> cheaters;
  10.  
  11. public static void main(String[] args) {
  12. testInput();
  13.  
  14. Scanner in = new Scanner(System.in);
  15.  
  16. cheaters = new HashMap<>();
  17.  
  18. int dependencies = Integer.parseInt(in.nextLine());
  19. String dependentsRelationship;
  20.  
  21. for (int i = 0; i < dependencies; i++) {
  22. dependentsRelationship = in.nextLine();
  23. String cheater = dependentsRelationship.substring(0, dependentsRelationship.indexOf(" "));
  24. dependentsRelationship = dependentsRelationship.substring(dependentsRelationship.indexOf(" ") + 1);
  25. String smartKid = dependentsRelationship.substring(0, dependentsRelationship.indexOf(" "));
  26. dependentsRelationship = dependentsRelationship.substring(dependentsRelationship.indexOf(" ") + 1);
  27. String subject = dependentsRelationship;
  28.  
  29. if (!cheaters.containsKey(subject)) {
  30. cheaters.put(subject, new HashMap<>());
  31. }
  32. if (!cheaters.get(subject).containsKey(cheater)) {
  33. cheaters.get(subject).put(cheater, new ArrayList<>());
  34. }
  35. cheaters.get(subject).get(cheater).add(smartKid);
  36. }
  37.  
  38. int m = Integer.parseInt(in.nextLine());
  39. for (int i = 0; i < m; i++) {
  40. String[] line = in.nextLine().split(" ");
  41. String parent = line[0];
  42.  
  43. String subjectStr = "";
  44. for (int j = 1; j < line.length; j++) {
  45. if (j != line.length - 1) {
  46. subjectStr += line[j] + " ";
  47. } else {
  48. subjectStr += line[j];
  49. }
  50. }
  51. String subject = subjectStr;
  52.  
  53. result.add(parent);
  54.  
  55. findDependencies(subject, parent);
  56. Collections.reverse(result);
  57. System.out.println(String.join(", ", result));
  58.  
  59. result = new ArrayList<>();
  60. visited = new HashSet<>();
  61.  
  62. }
  63. }
  64.  
  65. private static void findDependencies(String subject, String parent) {
  66.  
  67. if (!cheaters.get(subject).containsKey(parent)) {
  68. return;
  69. }
  70.  
  71. for (String dependence : cheaters.get(subject).get(parent)) {
  72. if (!visited.contains(dependence)) {
  73. result.add(dependence);
  74. visited.add(dependence);
  75. findDependencies(subject, dependence);
  76. }
  77. }
  78. }
  79.  
  80. private static void testInput() {
  81. String test = "7\n" +
  82. "Coki Doncho Math\n" +
  83. "Doncho Coki Graphs\n" +
  84. "Doncho Yana Math\n" +
  85. "Stamat Coki Graphs\n" +
  86. "Doncho Stamat Math\n" +
  87. "Doncho Coki Dynamic Programming\n" +
  88. "Stamat Yana Math\n" +
  89. "6\n" +
  90. "Coki Math\n" +
  91. "Doncho Math\n" +
  92. "Stamat Math\n" +
  93. "Stamat Graphs\n" +
  94. "Doncho Dynamic Programming\n" +
  95. "Coki Dynamic Programming";
  96. System.setIn(new ByteArrayInputStream(test.getBytes()));
  97. }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment