AcWing 846. java 行行注释详解
原题链接
简单
作者:
季之秋
,
2021-01-17 16:57:28
,
所有人可见
,
阅读 336
内部类
import java.util.*;
public class Main{
static int[] e,ne,h;//链接表 就是h的每个值都是一个链表的头指针
static int ans,idx,n;//ans是答案,idx是下标指针,n是结点数量
static boolean st[];//判断一个点有没有走过
static class Pair{
Pair(int N){//初始化数组
e=new int[N];
ne=new int[N];
h=new int[N];
st=new boolean[N];
Arrays.fill(h,-1);//里面每个值都是-1,表示空
}
void add(int a,int b){//在a的链表下插入一个值
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
ans=n;//也可以初始化ans=100000,
Pair q=new Pair(n*2);//开始初始化数组
for(int i=0;i<n-1;i++){
int a=sc.nextInt();
int b=sc.nextInt();
q.add(a,b);//无向图,所以a指向b,b也指向a
q.add(b,a);
}
dfs(1);//1的子节点数量(包括1自己),然后一直递归每一个有连接的点
System.out.println(ans);//输出所有最大连通块里面的最小值
}
static int dfs(int u){
st[u]=true;//走过u点
int ref=0,sum=0;//ref是最大当前连通块,sum是子节点数量的总和
for(int i=h[u];i!=-1;i=ne[i]){//从u开始走所有可以走到的点
int j=e[i];//1-n里面的值
if(!st[j]){//没走过的话
int t=dfs(j);//保存某一个子节点的数量
ref=Math.max(ref,t);//判断哪个子节点数量更多
sum+=t;//所有子节点的数量
}
}
ref=Math.max(ref,n-1-sum);//最大连通块,sum是子节点数量,n是总数量 1是节点本身
ans=Math.min(ref,ans);//所有最大连通块的最小值
return sum+1;//1是节点本身,sum是所有子节点数量;
}
}
void add(int a,int b){//在a的链表下插入一个值
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
这个能解释一下怎么插入值的吗,一直没看懂
详细的说明在数据结构里单链表的操作
好滴,那我去搜一下