在dfs实现中获取stackoverflowerr以获得非常大的输入

c0vxltue  于 2021-07-12  发布在  Java
关注(0)|答案(1)|浏览(413)

当使用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);
            }
        }
    }

}

错误日志

dxpyg8gm

dxpyg8gm1#

没有人回答我的问题,这个问题不是来自现场比赛,我花了一个星期的时间才想出解决问题的办法。stackoverflow的问题是由于HackerArth ide和类似的java联机ide上的堆栈调用次数限制,只允许10万次调用,为了避免这种情况,可以创建一个线程对象,手动传递stack size作为参数,这样会增加堆栈的大小。

class Solution{
     public static void main (String[] args) throws IOException {
          new Thread(null, new TestClass(), "", 1 << 26).start();
     }
     public void run() {
         // DO WHATEVER YOU WANT 
     }
}

相关问题