关于java 做图论题的时候,dfs总是爆栈报数组越界问题的解决方案,但是不知道原理,求大佬讲解
查看别人ac的java代码时,发现了一段神仙代码!!
public int solve (int n, int x, Point[] Edge) { try{ Thread t = new Thread(null,()->{ solve0(n, x, Edge); },"", 1 << 30); t.start(); t.join(); }catch(Exception e){ } // write code here return ans+1; }
大致意思就是将dfs的程序另开一个线程进行运行,然后我照着改了一下,居然真的过了真的过了!!
但是原理是什么呀?有没有大佬解释一下。
附上完整代码
import java.util.*; /* * public class Point { * int x; * int y; * } */ public class Solution { /** * 牛牛经过的房间数。 * @param n int整型 * @param x int整型 * @param Edge Point类一维数组 * @return int整型 */ ArrayList<Integer>[] map; void dfs(int node,int last,int[] dis){ for(int next:map[node]){ if(next==last)continue; dis[next]=dis[node]+1; dfs(next,node,dis); } } int ans=0; public void solve0 (int n, int x, Point[] Edge) { if(x==1){ ans=-1; return; } map=new ArrayList[n+1]; for(int i=1;i<=n;i++)map[i]=new ArrayList<>(); for(Point p:Edge){ map[p.y].add(p.x); map[p.x].add(p.y); } int[] dis1=new int[n+1]; int[] disx=new int[n+1]; //dis1[0]=disx[0]=-1; dfs(1,0,dis1); dfs(x,0,disx); for(int i=1;i<=n;i++){ if(dis1[i]>disx[i]) ans=Math.max(ans,dis1[i]); } } public int solve (int n, int x, Point[] Edge) { try{ Thread t = new Thread(null,()->{ solve0(n, x, Edge); },"", 1 << 30); t.start(); t.join(); }catch(Exception e){ } // write code here return ans+1; } }