今回は3問目を解き直します。
3問目の問題は こちら
自分の回答はTLEだったので性能をよくしたいと思っています。
public class Main {
public static void main(String[] args) {
HashMap<Integer, P> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
int result = 0;
// 整数の入力
int n = sc.nextInt();
int m = sc.nextInt();
IntStream.rangeClosed(0, n).forEach(i -> map.put(i, new P(i)));
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
map.get(a).putNext(b);
}
// 高橋君
map.get(0).putNext(0);
// 入力完了
for (int i = 1; i <= n; i++) {
boolean isOK = false;
for (int first : map.get(i).getNext()) {
for (int second : map.get(first).getNext()) {
for (int third : map.get(second).getNext()) {
if (third == 0) {
isOK = true;
}
}
}
}
System.out.println(isOK ? "Yes" : "No");
}
}
}
class P {
private int myNum;
private HashSet<Integer> set = new HashSet<>();
P(int a) {
myNum = a;
}
public void putNext(int next) {
set.add(next);
}
public HashSet<Integer> getNext() {
return set;
}
} クラスPを廃止してそのままHashSetにしたのと、最後でcontainsを使用してなんとかTLEじゃなくなりました。(1990ms、ぎりぎり)
printResultで、if文の中に入った場合にYesと出力してreturn;と書いてみたのですが、こちらだとなぜかTLE・・・なぜかはよく分からないです。。
public class Main {
public static void main(String[] args) {
HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
// 整数の入力
int n = sc.nextInt();
int m = sc.nextInt();
IntStream.rangeClosed(0, n).forEach(i -> map.put(i, new HashSet<>()));
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
map.get(a).add(b);
}
// 高橋君
map.get(0).add(0);
// 入力完了
for (int i = 1; i <= n; i++) {
printResult(i,map);
}
}
public static void printResult(int i, HashMap<Integer, HashSet<Integer>> map ) {
boolean isOK = false;
for (int first : map.get(i)) {
for (int second : map.get(first)) {
if (map.get(second).contains(0)) {
isOK = true;
}
}
}
System.out.println(isOK ? "Yes" : "No");
}
}う～ん、、TLEとの闘いはなかなか大変そうです。これだけでも結構時間かかってしまいました。
そもそもどうやれば効率よく処理できるかのセオリーの勉強が完全に足りない気がします。。引き続き精進します・・・