Submission #1148127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148127		ruben_ipenza	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	54 ms	11324 KiB

joi2019_ho_t4

package week05.laboratory;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class joi2019_ho_t4 {
  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    int t = Integer.parseInt(reader.readLine());
    for (int i = 0; i < t; i++) {
      HashMap<String, List<String>> directedGraph = new HashMap<>();
      HashMap<String, Boolean> visitedNodes = new HashMap<>();
      int m = Integer.parseInt(reader.readLine());
      for (int j = 0; j < m; j++) {
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        String from = tokenizer.nextToken();
        String to = tokenizer.nextToken();

        directedGraph.putIfAbsent(from, new ArrayList<>());
        directedGraph.putIfAbsent(to, new ArrayList<>());
        directedGraph.get(from).add(to);
      }

      boolean hasCycle = false;
      for (String drink : directedGraph.keySet()) {
        hasCycle = dfs(drink, directedGraph, visitedNodes);
        if (hasCycle) break;
      }

      writer.write("Case " + (i + 1) + ": ");
      if (hasCycle) {
        writer.write("No");
      } else {
        writer.write("Yes");
      }

      writer.newLine();
      writer.flush();
    }

    writer.close();
  }

  private static boolean dfs(
      String node,
      HashMap<String, List<String>> directedGraph,
      HashMap<String, Boolean> visitedNodes) {
    visitedNodes.put(node, true);

    for (String nextDrink : directedGraph.get(node)) {
      if (!visitedNodes.containsKey(nextDrink)) {
        if (dfs(nextDrink, directedGraph, visitedNodes)) {
          return true;
        }
      } else if (visitedNodes.get(nextDrink)) {
        return true;
      }
    }

    visitedNodes.put(node, false);
    return false;
  }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63