Counting Leaves (30)

public class Main {

private static int N;
private static int[][] FTree;
private static int[] numLevel;
private static int maxLevel;

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String str;
    String[] strs;

    int M;
    int vertex;

    while((str=br.readLine())!=null) {

        strs = str.split(" ");

        N = Integer.valueOf(strs[0]);
        M = Integer.valueOf(strs[1]);

        FTree = new int[100][N+1];

        for(int i=0; i<M; i++) {
            strs = br.readLine().split(" ");

            vertex = Integer.valueOf(strs[0]);
            for(int j=1; j<strs.length; j++) {
                FTree[vertex][j-1] = Integer.valueOf(strs[j]);
            }
        }

        numLevel = new int[M + 1];
        maxLevel = 0;

        preorder(1, 0);

        if(N == 0) {
            System.out.println(1);
            continue;
        }

        for(int i=0; i<maxLevel; i++) {
            System.out.print(numLevel[i] + " ");
        }
        System.out.println(numLevel[maxLevel]);
    }

}

private static void preorder(int root, int level) {
    if(FTree[root][0]==0) {
        numLevel[level]++;
        if(maxLevel < level) {
            maxLevel = level;
        }
    } else {
        int K = FTree[root][0];
        for(int k=1; k<=K; k++) {
            preorder(nextNode(root, k), level+1);
        }
    }
}

private static int nextNode(int root, int k) {
    if(k<=FTree[root][0]) {
        return FTree[root][k];
    }
    return 0;
}

}

//BFS import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class test1004 {
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//注意while处理多个case
        		String s=in.nextLine();
        		String[] r=s.split(" ");
        		int a=Integer.parseInt(r[0]);
        		int b=Integer.parseInt(r[1]);
        		int index=0;
        		if(b==0) {
        			System.out.println(1);
        			continue;
        		}
        		ArrayList<Integer>[] arr=new ArrayList[a+1];
        		for (int i = 0; i < arr.length; i++) {
					arr[i]=new ArrayList<Integer>();
				}
            while(index++<b){
            	String temp=in.nextLine();
            	String[] s1=temp.split(" ");
            	int index1=Integer.parseInt(s1[0]);
            	for (int i = 2; i < s1.length; i++) {
					arr[index1].add(Integer.parseInt(s1[i]));
				}
            }
            do_1(a,b,arr);
        }
	
	}

	private static void do_1(int a, int b, ArrayList<Integer>[] arr) {
		Queue<Integer> queue=new LinkedList<Integer>();
		queue.add(1);
		int depth=0;
		int[] res=new int[a];
		while(!queue.isEmpty()){
			int size=queue.size();
			for (int i = 0; i < size; i++) {
				int temp=queue.remove();
				if(arr[temp].size()==0) res[depth]++;
				for (int j = 0; j <arr[temp].size(); j++) {
					queue.add(arr[temp].get(j));
				}
			}
			depth++;
		}
		for (int i = 0; i < depth-1; i++) {
			System.out.print(res[i]+" ");
		}
		System.out.print(res[depth-1]);
	}
} 

#include<iostream>
using namespace std;
int main()
{ int a[101][101]={0},m,n,i,j,p,q,s,t,k[101]={0};//数组k来记录每一层叶节点数
cin>>n>>m;
a[1][0]=1;//这个二维数组建立的比较巧妙，用a[i][0]记录该节点的层数,用a[i][j]=1表示i，j联接
for(i=1;i<=m;i++)
{
cin>>s>>t;
for(j=1;j<=t;j++)
{
cin>>p;
a[s][p]=1;
a[p][0]=a[s][0]+1;
}
if(q<a[s][0]+1) q=a[s][0]+1;
}
for(i=1;i<=n;i++)
{
p=1;
if(a[i][0])
{
while(p<=n&&!a[i][p]) p++;
if(p==n+1) k[a[i][0]]++;/判断i是否为叶节点，若是则i对应的层数叶子节点数加一
}
}
for(i=1;i<=q;i++)
{
if(i<q) cout<<k[i]<<" ";
if(i==q) cout<<k[i];
}
return 0;
}

思路 问题是求没有孩子的节点的每一层的个数
方法 1.建立这棵树  以二维可变数组，父节点存储了子节点的id
     2.深度遍历这颗树得到，树的高度，和每层的树的没有孩子的个数。
输出这个树所有的没有孩子节点的个数
#include <iostream>
#include <vector>
using namespace std; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
vector<int> parent[110];
int hashLevel[110]={0};
int maxLevel = 0;
void DFS(int root, int level)
{
    if(level > maxLevel)
    {
        maxLevel = level;
    }
    if(parent[root].size() == 0)
    {
        hashLevel[level]+=1;
    }
    else
    {
        for(int i=0; i<parent[root].size(); i++)
        {
            DFS(parent[root][i], level+1);
        }
    }
}
int main(int argc, char** argv) {
    int N,M;
    cin >> N >> M;
    
    int parents,num,children;
    for(int i=0; i<M; i++)
    {
        cin >> parents >> num;
        for(int j=0; j<num; j++)
        {
            cin >> children;
            parent[parents].push_back(children);
        }
    }
    DFS(1,1);
    for(int j=1; j<=maxLevel; j++)
    {
        cout << hashLevel[j];
        if(j!=maxLevel)
        {
            cout << " ";
        }
    } 
    cout << endl; 
    return 0;
}

#include<cstdio>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=110;
vector<int> child[maxn];
int hashTable[maxn]={0};
int level[100]={0};
int maxlevel=0;
int N,M;
int ans=0;
void BFS(int root)
{
    queue<int> q;
    q.push(root);
    level[1]=1;
    while(!q.empty())
    {
        int node=q.front();
        q.pop();
        if(child[node].size()==0)  hashTable[level[node]]++;
        for(int i=0;i<child[node].size();i++)
        {
            level[child[node][i]]=level[node]+1;  //记录每个节点在第几层
            if(level[child[node][i]]>maxlevel) maxlevel=level[child[node][i]]; 
            q.push(child[node][i]);
        }
    }
}
void DFS(int root,int level)
{
    if(level>maxlevel) maxlevel=level;
    if(child[root].size()==0) hashTable[level]++;
    for(int i=0;i<child[root].size();i++)
       DFS(child[root][i],level+1);
}
int main()
{
    cin>>N>>M;
    int parent,num;
    for(int i=1;i<=M;i++)
    {
        cin>>parent>>num;
        for(int i=0;i<num;i++)
        {
            int ch;cin>>ch;
            child[parent].push_back(ch);
        }
    }
    //BFS(1);
    DFS(1,1);
    for(int i=1;i<=maxlevel;i++)
    {
     cout<<hashTable[i];
     if(i!=maxlevel) cout<<" ";
    }
}

 import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// N为所有节点数，M为所有非叶节点数
		//Scanner的nextInt方法和nextLine不能混用！！
		String[] s=sc.nextLine().split(" ");
		int N = Integer.parseInt(s[0]), M = Integer.parseInt(s[1]);
		// 用一个ArrayList数组来保存每一个节点的子节点.节点从1开始，所以lists大小为N+1
		ArrayList<Integer>[] lists = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) {
			lists[i] = new ArrayList<Integer>();
		}
		// 循环读取输入
		for (int i = 0; i < M; i++) {
			// 将字符串以空格分割，结果为String数组
			String str=sc.nextLine();
			String[] strs = str.split(" ");
			for (int j = 2; j < strs.length; j++) {
				lists[Integer.parseInt(strs[0])].add(Integer.parseInt(strs[j]));
			}
		}
		// 广度优先搜索
		List<Integer> res = bfs(lists);

		for (int i = 0; i < res.size() - 1; i++) {
			System.out.print(res.get(i) + " ");
		}
		System.out.print(res.get(res.size() - 1));
	}

	private static List<Integer> bfs(ArrayList<Integer>[] lists) {
		// 树的层序遍历，需要借助队列完成
		Queue<Integer> queue = new LinkedList<Integer>();
		// res存储每层叶节点数
		List<Integer> res = new ArrayList<Integer>();
		queue.add(1);
		while (!queue.isEmpty()) {
			int count = 0, size = queue.size();
			for (int i = 0; i < size; i++) {
				int tmp = queue.poll();
				if (lists[tmp].isEmpty()) {
					count++;
				} else {
					for (Integer num : lists[tmp])
						queue.add(num);
				}

			}
			res.add(count);
		}
		return res;

	}

} 

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 100 + 2;
int level[maxn], leaf_num[maxn];
vector<int> tree[maxn];
int max_level = 0;

void level_order(int root){
	queue<int> q;
	q.push(root);
	level[root] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(unsigned int i=0; i<tree[u].size(); i++){
			int v = tree[u][i];
			level[v] = level[u] + 1;
			max_level = (max_level > level[v]) ? max_level : level[v];
			if(tree[v].size() == 0) leaf_num[level[v]] += 1;
			q.push(v);
		}
	}
}

int main(){
	int n, m;
	memset(leaf_num, 0, sizeof(leaf_num));
	scanf("%d %d", &n, &m);
	if(n==1 && m==0) printf("1\n");
	else{
		//level[1] = 1;
		for(int i=0; i<m; i++){
			int node, k;
			scanf("%d %d", &node, &k);
			for(int j=0; j<k; j++){
				int child;
				scanf("%d", &child);
				//level[child] = level[node] + 1;
				//max_level = (max_level > level[child]) ? max_level : level[child];
				tree[node].push_back(child);
			}
		}
		level_order(1);
		printf("%d", leaf_num[1]);
		for(int i=2; i<= max_level; i++){
			printf(" %d", leaf_num[i]);
		}
		printf("\n");
	}
	return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//可注意这道题输入的读取方式
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		String[] r = in.nextLine().trim().split(" ");
		int N = Integer.parseInt(r[0]); // 树中的节点的数目
		int M = Integer.parseInt(r[1]); // 树中非叶子节点的数目（有孩子的节点）
			
		if(M==0){
			System.out.println(1);
			return;
		}
		// 注意这种写法，首先它是一个固定长的数列，然后里面的对象是ArrayList型的，ArrayList里面的数是整数型的
		ArrayList<Integer>[] arr = new ArrayList[N+1];  //矩阵的长度为N+1，即树的节点数目加一，即从0-N
		for(int i=0;i<arr.length;i++){
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<M;i++){
			String[] line = in.nextLine().trim().split(" ");
			// 得到孩子数目
			int index1 = Integer.parseInt(line[0]);    // 现在处理的是节点index1
			for(int j=2;j<line.length;j++){
				arr[index1].add(Integer.parseInt(line[j]));
			}
		}	
		BFS(N,M,arr);
	}
	// BFS 广度优先搜索
	private static void BFS(int N,int M,ArrayList<Integer>[] arr){
		// 
		Queue<Integer> queue = new LinkedList<Integer>();   // Queue是一个接口，不能实例化
		queue.add(1);  //
		int depth=0;   // 属于第几层
		int[] res = new int[N];   // 每一深度没有孩子节点的数目
		while(!queue.isEmpty()){  // 若不空
			int size = queue.size();
			for(int i=0;i<size;i++){
				int temp = queue.remove();
				if(arr[temp].size()==0)  // 当前节点没有孩子
					res[depth]++;        // 这一深度无孩子的节点增加
				for(int j=0;j<arr[temp].size();j++){
					queue.add(arr[temp].get(j));
				}
					
			}
			depth++;
		}
		for(int i=0;i<depth-1;i++){
			System.out.print(res[i]+" ");
		}
		System.out.print(res[depth-1]);
		
	}
}

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=105;
int n,m,level=0;
vector<int>v[maxn],cnt;
void solve(){
    int leftNum=1,curNum=0,tot=0,root,len;
    queue<int>q;
    q.push(1);
    if(v[1].size()==0){
        tot++;
    }
    cnt.push_back(tot);
    tot=0;
    while(!q.empty()){
        root=q.front();
        q.pop();
        leftNum--;
        len=v[root].size();
        curNum+=len;
        for(int i=0;i<len;i++){
            if(v[v[root][i]].size()==0){
                tot++;
            }
            q.push(v[root][i]);
        }
        if(leftNum==0){
            //处理最后一层
            if(curNum){
                leftNum=curNum;
                curNum=0;
                cnt.push_back(tot);
                tot=0;
            }
        }
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    int num,fa,child;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&fa,&num);
        for(int i=0;i<num;i++){
            scanf("%d",&child);
            v[fa].push_back(child);
        }
    }
    solve();
    printf("%d",cnt[0]);
    for(int i=1;i<cnt.size();i++){
        printf(" %d",cnt[i]);
    }
    printf("\n");
    return 0;
}

是个树就能DFS😍
#include<bits/stdc++.h>
using namespace std;

const int Max=110;
vector<int> child[Max];
int Hashtable[Max];
int depth=0;

void DFS(int index,int level) {
	depth=max(depth,level);
	if(child[index].size()==0){
		Hashtable[level]++;
	}
	for(int i=0;i<child[index].size();i++){
		DFS(child[index][i],level+1);
	}
}

int main() {
	int n,m,k,father,ch;
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++) {
		scanf("%d %d",&father,&k);
		for(int j=0; j<k; j++) {
			scanf(" %d",&ch);
			child[father].emplace_back(ch);
		}
	}
	DFS(1,1);
	for(int i=1; i<=depth; i++) {
		printf("%d",Hashtable[i]);
		if(i<depth) printf(" ");
	}
	printf("\n");
	return 0;
}

解决问题

       通过树的层次遍历，求每一层的无后代节点个数

题目描述

A family hierarchy is usually presented by a pedigree tree.  Your job is to count those family members who have no child.

输入描述

Each 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.

输出描述

For 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.

输入例子

2 1

01 1 02

输出例子

0 1

代码实现

#include<bits/stdc++.h>

using namespace std;

int N,M;

struct Node{

    int layer;

    vector<int> child;

}node[108];

void LayerOrder(int root)

{

    queue<int> Q;

    Q.push(root);

    node[root].layer=0;

    while(!Q.empty())

    {

        int _front=Q.front();

        Q.pop();

        for(int i=0;i<node[_front].child.size();i++)

        {

            int child=node[_front].child[i];

            node[child].layer=node[_front].layer+1;

            Q.push(child);

        }

    }

}

int main()

{

    cin>>N>>M;

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

    {

        int id,K;

        cin>>id>>K;

        for(int j=0;j<K;j++)

        {

            int x;

            cin>>x;

            node[id].child.push_back(x);

        }

    }

    LayerOrder(1);

    int num=-1;

    for(int i=1;i<=N;i++)

    {

        if(num<node[i].layer)

        {

            num=node[i].layer;

        }

    }

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

    {

        int sum=0;

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

        {

            if(node[j].layer==i&&node[j].child.size()==0)

            {

                sum++;

            }

        }

        cout<<sum;

        if(i!=num)

        {

            cout<<" ";

        }

    }

    return 0;

}

#include<cstdio>
(802)#include<vector>
#include<queue>
(789)#include<algorithm>
using namespace std;
const int maxn=110;
struct node
{
    int id;
    int level;
    node(){}
    node(int _id,int _level):id(_id),level(_level){}
};
vector<int> tree[maxn];
int ans[maxn];
int level;
void BFS()
{
    fill(ans,ans+maxn,0);
    queue<node> qu;
    qu.push(node(1,0));
    level=0;
    while(!qu.empty())
    {
        node nownode=qu.front();
        qu.pop();
        int v=nownode.id,l=nownode.level;
        level=max(level,l);
        if(tree[v].size()==0)
            ans[l]++;
        for(int i=0;i<tree[v].size();i++)
        {
            int next=tree[v][i];
            int nextl=l+1;
            qu.push(node(next,nextl));
        }
    }
}
int main()
{
    int n=0;
    scanf("%d",&n);
    if(n==0)    return 0;
    int m=0,id=0,k=0;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&id,&k);
        int child=0;
        while(k--)
        {
            scanf("%d",&child);
            tree[id].push_back(child);
        }
    }
    BFS();
    for(int i=0;i<=level;i++)
    {
        if(i)   printf(" ");
        printf("%d",ans[i]);
    }
    printf("\n");
    return 0;
}

/***************************************************************************
本题使用的数据结构为：邻接表；
在创建邻接表的过程中，同时将该数据所在的层也加入邻接表中；
具体方法：加入邻接表头插法，其邻接表头和字节点为父子关系，即表头的层总是比节
         点元素大一；根据这个关系，每个数据所在的层将录入邻接表；
         接下来是遍历这个邻接表，count[children[i].level] ++;最后输出count
         里面的元素即可；
****************************************************************************/
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;

int maxlevel = 1;
//数据结构：邻接表
typedef struct Child {
    int ID;
    Child *next;
    Child()
    {
        ID = 0;
        next = NULL;
    }
};
typedef struct Member {
    int level;//表头元素所在层
    int child_num;
    Child  *Mchild;
    Member()
    {
        level = 0; 
        child_num = 0;
        Mchild = NULL;
    }
}*memeber;

int main()
{
    int node_num, noLeaf_node;
    int num_level, child_num, v_child;
    int count[100] = { 0 };
    
    
    Child *new_child = NULL;
    cin >> node_num >> noLeaf_node;
    
    vector<Member>children(node_num+1);

    children[1].level = 0;
    for (int i = 0; i < noLeaf_node; i++) {
        cin >> num_level >> v_child;
        
        for (int j = 0; j < v_child; j++) {
            new_child = new Child;
            cin >> new_child->ID;
            new_child->next = children[num_level].Mchild;
            children[num_level].Mchild = new_child;
            children[num_level].child_num++;
            children[new_child->ID].level = children[num_level].level + 1;
        }
    }

    int temp_level = 0;
    for (int i = 1; i <= node_num; i++) {
        if (children[i].level > temp_level)
            temp_level = children[i].level;
        if (children[i].Mchild == NULL)
            count[children[i].level] ++;
    }
    int i = 0;
    for ( i = 0; i < temp_level; i++)
        cout << count[i] << " ";
    cout << count[i] << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
const int maxn=110;
int n,m,leafnode[maxn]={0},levelnum=1;       //leafnode[]存放每层叶子结点数，levelnum为树的总层数
vector<int> Node[maxn];
void DFS(int now,int level){
    if(Node[now].size()==0)                  //若当前结点为叶结点
        leafnode[level]++;
    if(level>levelnum)                       //更新树的总层数
        levelnum=level;
    for(int i=0;i<Node[now].size();i++)
        DFS(Node[now][i],level+1);
}
int main(){
    cin>>n>>m;
    int father,childnum,child;
    for(int i=0;i<m;i++){
        cin>>father>>childnum;
        for(int j=0;j<childnum;j++){
            cin>>child;
            Node[father].push_back(child);
        }
    } 
    DFS(1,1);                                //根结点为1号，在第一层
    cout<<leafnode[1];
    for(int i=2;i<=levelnum;i++)
        cout<<" "<<leafnode[i];
    return 0;
}