DFS 在图形中找到网桥时进行堆栈溢出

Question

我的DFS在图形中找到网桥时正在经历堆栈溢出。在这个问题中，我得到了边以及它们的 id 在具有顶点(1 到 n(的图中。我需要找出与给定 id(q 查询(关联的边缘是否是桥接器。请帮助我了解我的代码出了什么问题：

import java.util.*;
class TestClass {
static int time=0;
static class pair{
int v,id;
pair(int v,int id){
this.v=v;
this.id=id;
}
}
static class graph{
static int v;
static ArrayList<pair>[] adj;
graph(int v){
this.v=v;
adj=new ArrayList[v+1];
for(int i=1;i<=v;i++)
adj[i]=new ArrayList<pair>();
}
static void addedge(int u,int v,int id){
adj[u].add(new pair(v,id));
adj[v].add(new pair(u,id));
}
}
static void dfs(graph g,int[] disc,int[] low,int[] parent,boolean[] visited,boolean[] bridge,int src){
visited[src]=true;
disc[src]=low[src]=++time;
for(pair p:g.adj[src]){
int i=p.v;
int id=p.id;
if(!visited[i]){
//System.out.println(i);
parent[i]=src;
dfs(g,disc,low,parent,visited,bridge,i);
low[src]=Math.min(low[src],low[i]);
if(low[i]>disc[src]){
bridge[id]=true;
}
}
else if(parent[src]!=i){
low[src]=Math.min(low[src],disc[i]);
}
}
}
public static void main(String args[] ) throws Exception {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int q=input.nextInt();
graph g=new graph(n);
for(int i=0;i<m;i++){
int u=input.nextInt();
int v=input.nextInt();
int id=input.nextInt();
g.addedge(u,v,id);
}
int[] disc=new int[n+1];
int[] parent=new int[n+1];
int[] low=new int[n+1];
boolean[] visited=new boolean[n+1];
boolean[] bridge=new boolean[m+1];
for(int i=1;i<=n;i++){
if(!visited[i]){
parent[i]=-1;
dfs(g,disc,low,parent,visited,bridge,i);
}
}
while(q-->0){
int i=input.nextInt();
if(bridge[i])
System.out.println("YES");
else
System.out.println("no");
}
}
}

Answer 1

请帮助我了解我的代码出了什么问题

我无法阅读的代码太多了...并对您的意图进行逆向工程。

当递归算法递归太深并填充堆栈时，通常会发生StackOverflowError。 例如：

// This is a recursive infinite loop.  It will throw SOE
public void callMe() {
callMe();
}
// This is a finite loop but it may throw SOE if 'n' is too big 
// or if it is negative
public void countDown(int n) {
if (n != 0) {
countDown(n - 1);
}
}

这是一般的想法...

---

要在代码中查找问题的原因，请执行以下操作：

1. 检查堆栈跟踪。 这将告诉您深度递归涉及哪些方法和哪些代码行。

2. 检查代码，看看是否可以发现明显的错误。

3. 在 IDE 的调试器中运行代码。 在键方法(涉及递归(处设置断点，并使用调试器的函数显示局部变量以尝试了解正在发生的事情。dfs方法是设置断点的好地方。

4. 如果 3 没有启发性，请向代码添加一些跟踪打印，以帮助您弄清楚发生了什么。 例如，在每个dfs调用开始时打印src的值。