当使用java在HackerArth上实践dfs问题时,其中一个测试用例导致nzec错误,当检查它时,它显示stackoverflow错误。我检查了很多次,但是所有的测试用例都通过了,除了一个导致错误的测试用例,这不是针对那个特定的问题,而是针对许多问题(dfs问题),在用java解决时,10个或20个测试用例中总是有一个会导致nzec。
我不知道这是由于我的邻接列表实现还是其他原因。这就是问题之一。
问题:https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/feasible-relations/
我的代码:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;
public class TestClass {
static long mod = 1000000007;
static String[] temp;
static int[] node;
static int[] vis;
public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main (String[] args) throws IOException {
int testCases= Integer.parseInt(br.readLine().split(" ")[0]);
while (testCases > 0) {
temp = br.readLine().split(" ");
int N = Integer.parseInt(temp[0]);
int K = Integer.parseInt(temp[1]);
HashMap<Integer, ArrayList<Integer>> forEqual = new HashMap<>();
ArrayList<int[]> edgeList = new ArrayList<>();
for (int i = 0; i < K; i++) {
temp = br.readLine().split(" ");
int u = Integer.parseInt(temp[0]);
int v = Integer.parseInt(temp[2]);
if (temp[1].equals("=")) {
forEqual.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
forEqual.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
} else {
edgeList.add(new int[]{u, v});
}
}
boolean[] vis = new boolean[1000005];
node = new int[1000005];
int c = 0;
for (int i : forEqual.keySet()) {
if (!vis[i]) {
c++;
DFS(i, forEqual, c, vis);
}
}
boolean flag = true;
for(int[] i : edgeList){
if(node[i[0]] == node[i[1]]){
flag = false;
break;
}
}
System.out.println(flag ? "YES" : "NO");
testCases--;
}
}
private static void DFS(int i, HashMap<Integer, ArrayList<Integer>> forEqual, int c, boolean[] vis) {
vis[i] = true;
node[i] = c;
for (int v : forEqual.get(i)) {
if (!vis[v]) {
DFS(v, forEqual, c, vis);
}
}
}
}
错误日志
1条答案
按热度按时间dxpyg8gm1#
没有人回答我的问题,这个问题不是来自现场比赛,我花了一个星期的时间才想出解决问题的办法。stackoverflow的问题是由于HackerArth ide和类似的java联机ide上的堆栈调用次数限制,只允许10万次调用,为了避免这种情况,可以创建一个线程对象,手动传递stack size作为参数,这样会增加堆栈的大小。