1004. Counting Leaves (30)
题目阐述
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
InputEach input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.
OutputFor each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.
Sample Input
2 1
01 1 02
Sample Output
0 1
- 原题链接
题目分析
这是道族谱图分析题，背后的知识的考察的图的基础层次遍历，广度搜索等知识。
下面是使用深搜DFS的代码：
package PAT;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {
static int N, max;static List<Integer>[] list;static int[] arr;public static void main(String[] args) {Scanner s = new Scanner(System.in);N = s.nextInt();int M = s.nextInt();list = new ArrayList[N];arr = new int[N];for(int i=0; i<list.length; i++)list[i] = new ArrayList<Integer>();for(int i=0; i<M; i++) {int k = s.nextInt() - 1;int n = s.nextInt();for(int j=0; j<n; j++)list[k].add(s.nextInt() - 1);}s.close();dfs(0, 0);for(int i=0; i<=max; i++) {if(i == 0) System.out.print(arr[i]);else System.out.print(" " + arr[i]);}}private static void dfs(int k, int depth) {if(list[k].size() == 0) {arr[depth] ++;if(depth > max)max = depth;return;}for(int i : list[k]) {dfs(i, depth + 1);}}}
下面是使用广搜BFS算法实现的，不过运行的时候在一个2分的点出错了，但是目前还没找出错误在哪里。先附上代码把；
package PAT;import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;public class CoutingLeaves {
static int N, M;static List<Integer>[] list;public static void main(String[] args) {Scanner s = new Scanner(System.in);N = s.nextInt();M = s.nextInt();list = new ArrayList[N];for(int i=0; i<list.length; i++)list[i] = new ArrayList<Integer>();for(int i=0; i<M; i++) {int k = s.nextInt() - 1;int n = s.nextInt();for(int j=0; j<n; j++)list[k].add(s.nextInt() - 1);}Queue<Integer> queue = new LinkedList<Integer>();queue.add(0);int num = 1, temp = 0, depth = 0, total = 0;int[] arr = new int[N];while(!queue.isEmpty()) {int index = queue.poll();num --;if(list[index].size() == 0)total ++;for(int i=0; i<list[index].size(); i++)queue.add(list[index].get(i));temp += list[index].size();if(num == 0) {num = temp;temp = 0;arr[depth ++] = total;total = 0;}}for(int i=0; i<depth; i++) {if(i == 0) System.out.print(arr[i]);else System.out.print(" " + arr[i]);}}}