关于java 做图论题的时候,dfs总是爆栈报数组越界问题的解决方案,但是不知道原理
锻炼身体
https://ac.nowcoder.com/acm/contest/6914/C
关于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;
}
}