Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.company;
- import java.io.ByteArrayInputStream;
- import java.util.*;
- public class Cheaters {
- private static Set<String> visited = new HashSet<>();
- private static List<String> result = new ArrayList<>();
- private static Map<String, Map<String, List<String>>> cheaters;
- public static void main(String[] args) {
- testInput();
- Scanner in = new Scanner(System.in);
- cheaters = new HashMap<>();
- int dependencies = Integer.parseInt(in.nextLine());
- String dependentsRelationship;
- for (int i = 0; i < dependencies; i++) {
- dependentsRelationship = in.nextLine();
- String cheater = dependentsRelationship.substring(0, dependentsRelationship.indexOf(" "));
- dependentsRelationship = dependentsRelationship.substring(dependentsRelationship.indexOf(" ") + 1);
- String smartKid = dependentsRelationship.substring(0, dependentsRelationship.indexOf(" "));
- dependentsRelationship = dependentsRelationship.substring(dependentsRelationship.indexOf(" ") + 1);
- String subject = dependentsRelationship;
- if (!cheaters.containsKey(subject)) {
- cheaters.put(subject, new HashMap<>());
- }
- if (!cheaters.get(subject).containsKey(cheater)) {
- cheaters.get(subject).put(cheater, new ArrayList<>());
- }
- cheaters.get(subject).get(cheater).add(smartKid);
- }
- int m = Integer.parseInt(in.nextLine());
- for (int i = 0; i < m; i++) {
- String[] line = in.nextLine().split(" ");
- String parent = line[0];
- String subjectStr = "";
- for (int j = 1; j < line.length; j++) {
- if (j != line.length - 1) {
- subjectStr += line[j] + " ";
- } else {
- subjectStr += line[j];
- }
- }
- String subject = subjectStr;
- result.add(parent);
- findDependencies(subject, parent);
- Collections.reverse(result);
- System.out.println(String.join(", ", result));
- result = new ArrayList<>();
- visited = new HashSet<>();
- }
- }
- private static void findDependencies(String subject, String parent) {
- if (!cheaters.get(subject).containsKey(parent)) {
- return;
- }
- for (String dependence : cheaters.get(subject).get(parent)) {
- if (!visited.contains(dependence)) {
- result.add(dependence);
- visited.add(dependence);
- findDependencies(subject, dependence);
- }
- }
- }
- private static void testInput() {
- String test = "7\n" +
- "Coki Doncho Math\n" +
- "Doncho Coki Graphs\n" +
- "Doncho Yana Math\n" +
- "Stamat Coki Graphs\n" +
- "Doncho Stamat Math\n" +
- "Doncho Coki Dynamic Programming\n" +
- "Stamat Yana Math\n" +
- "6\n" +
- "Coki Math\n" +
- "Doncho Math\n" +
- "Stamat Math\n" +
- "Stamat Graphs\n" +
- "Doncho Dynamic Programming\n" +
- "Coki Dynamic Programming";
- System.setIn(new ByteArrayInputStream(test.getBytes()));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment