迷之RE祭。

一道简单的树形数据结构练手题。

难度：橙色的

题面描述

给定一棵树，输出树的根$root$，孩子最多的结点$max$以及他的孩子。

输入输出格式

输入格式

第一行：$n$(结点个数$\leq 100$)，$m$(边数$\leq200$)。
以下$m$行：每行两个结点$x$和$y$，表示$y$是$x$的孩子($x,y \leq 100$)。

输出格式

第一行：树根：$root$；第二行：孩子最多的结点$max$（多个只输出编号最小的结点）；第三行：$max$的孩子（按编号由小到输出）。

INPUT & OUTPUT’s example

Input’s example #1

Output’s example #1

1
2
3

4
2
6 7 8

提示

分析

本题十分简单，也证明Herself32实在是太蒻了。

还是再说几句吧。

首先我们开一个struct来存储当前节点的父亲和儿子，然后用结构体变量tree[MAXN]来初始化。

因为根节点没有父亲节点，所以我们遍历每一个节点，如果tree[i].father==0那么根节点就找到了。

处理孩子最多的节点时，我们就可以遍历一遍节点，将struct里面存放的节点数目最大值求出来，然后根据下标对应输出这个节点的孩子。

代码实现

/* Headers */
#include<cstdio>
#include<cstring>
#include<cctype> 
#include<iostream>
#include<cmath>
/* define */
#define MAXN 111
using namespace std;
namespace FastIO{
	const int BUFSIZE=(1<<20);
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++; 
	}
	inline int getint(){
		int neg=0,res=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF){
			ch=getch();
		}
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
		} 
		return neg?-res:res;
	}
	inline void write(int x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
	inline void space(int x){
		if(x==0)putchar(' ');
		else putchar('\n');
	}
}
using namespace FastIO;
/* definitions */
struct Node{
	int father;
	int kid,child[MAXN];
};
Node tree[MAXN];
int rt,maxkid;
int n,m,x,y;
int Max,cnt;
/* functions */
inline void Build(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		tree[y].father=x;
		tree[x].kid++;
		tree[x].child[tree[x].kid]=y;
	}
}
inline void findrt(){
	for(int i=1;i<=n;i++){
		if(tree[i].father==0){
			rt=i;break;
		}
	}
} 
inline void findkid(){
	for(int i=1;i<=n;i++){
		maxkid=max(maxkid,tree[i].kid);
	}
	for(int i=1;i<=n;i++){
		if(tree[i].kid==maxkid){
			Max=i;
			break;
		}
	} 
}
inline void printkids(){
	for(int i=1;i<=n;i++){
		if(tree[i].kid==maxkid){
			for(int j=1;j<=maxkid;j++){
				printf("%d ",tree[i].child[j]);
			}
			break;
		}
	} 
} 
inline void print(){
	printf("%d\n",rt);
	printf("%d\n",Max);
} 
int main(int argc, char *argv[]){
	Build();
	findrt();
	findkid();
	print();
	printkids();
	return 0;
}

CD2018/12/8A题解