队列DFS和用数组存储的树（Java）

解题思路:先通过构造一棵树，这里用数组记录数的父节点最为合适，且需开第二个数组记录该节点的后代节点个数，在构造一个队列，用于DFS，在遍历每一层的时候去掉这一层中后代节点数最大的节点，最后加上每层遍历后队列元素数量。

注意事项:

参考代码:

import java.util.Scanner;

import java.util.ArrayList;

public class Main {

    static Scanner sc1=new Scanner(System.in);

public static void main(String[] args) {

// TODO Auto-generated method stub

int n=sc1.nextInt(),p=sc1.nextInt();

myclass m1=new myclass(n,p);

      System.out.println(m1.dfs());

} 

}

class myclass{

int n;

int[] sz;//记录父节点index

int[] szsz;//记录后代节点个数

public myclass(int n1,int p)

{

n=n1;

sz=new int[n+1];

szsz=new int[n+1];

int z,y;

for(int i=0;i<n+1;i++)

{

szsz[i]=1;

sz[i]=0;

}

for(int i=0;i<p;i++)

{

z=Main.sc1.nextInt();

y=Main.sc1.nextInt();

if(z<y)

{

sz[y]=z;

for(int i1=z;sz[i1]!=i1;i1=sz[i1])

{

szsz[i1]+=szsz[y];

}

}

else

{

sz[z]=y;

for(int i1=y;sz[i1]!=i1;i1=sz[i1])

{

szsz[i1]+=szsz[z];

}

}

}

}

int dfs()//

{

int ans=1;

ArrayList<Integer> l1=new ArrayList<Integer>();

l1.add(1);

l1.add(-1);

int c=0;

while(!l1.isEmpty())

{

int max=0,maxh=0,maxhh=0;

for(;;)

{

c=l1.remove(0);

if(-1==c&&l1.size()==0) return ans;

if(-1==c) 

{

l1.remove(maxhh);

ans+=l1.size();

l1.add(-1);

break;

}

for(int j=1;j<n+1;j++)

{

if(c==sz[j])

{

l1.add(j);

if(szsz[j]>max)

{

max=szsz[j];

maxhh=maxh;

}

maxh++;

}

}

}

}

return ans;

}

}