首页 > 代码库 > NBUT 1186 Get the Width（DFS求树的宽度，水题）
NBUT 1186 Get the Width（DFS求树的宽度，水题）
[1186] Get the Width
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
- It‘s an easy problem. I will give you a binary tree. You just need to tell me the width of the binary tree.
The width of a binary tree means the maximum number of nodes in a same level.
For example, the width of binary tree above is 3.
- 输入
- The first line is an integer T, means the number of cases.
Then follow T cases.
For each case, the first line is an integer N, means the number of nodes. (1 <= N <= 10)
Then follow N lines. Each line contains 3 integers P A B; indicate the number of this node and its two children node. If the node doesn’t have left child or right child, then replace it by -1.
You can assume the root is 1.
- 输出
- For each case, output the width.
- 样例输入
164 -1 -12 4 55 -1 -11 2 36 -1 -13 -1 6
- 样例输出
3
题目链接：NBUT 1186
闲来无事水一发简单的= =，听说大二要学数据结构，原来树的宽度是这么个意思，建图dfs一下即可
代码：
#include<stdio.h>#include<iostream>#include<algorithm>#include<cstdlib>#include<sstream>#include<cstring>#include<bitset>#include<string>#include<deque>#include<stack>#include<cmath>#include<queue>#include<set>#include<map>using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=100010;struct edge{ int to; int pre;};edge E[N];int head[N],tot;int cnt[N],vis[N];void add(int s,int t){ E[tot].to=t; E[tot].pre=head[s]; head[s]=tot++;}void init(){ CLR(cnt,0); CLR(head,-1); tot=0; CLR(vis,0);}void dfs(int cur,int dep){ ++cnt[dep]; vis[cur]=1; for (int i=head[cur]; ~i; i=E[i].pre) { int son=E[i].to; if(!vis[son]) dfs(son,dep+1); }}int main(void){ int tcase,i,j,n,p,a,b; scanf("%d",&tcase); while (tcase--) { init(); scanf("%d",&n); while (n--) { scanf("%d%d%d",&p,&a,&b); if(a!=-1) add(p,a); if(b!=-1) add(p,b); } dfs(1,1); printf("%d\n",*max_element(cnt+1,cnt+N)); } return 0;}NBUT 1186 Get the Width（DFS求树的宽度，水题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。