当前位置：网站首页>上课笔记(7)(1)——＃647. 找树根和孩子(root)

上课笔记(7)(1)——＃647. 找树根和孩子(root)

2022-08-10 07:31:00 【xyc20120615】

Description

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

Format

Input

第一行：n（结点数≤100），m（边数≤200）。

以下 m 行；每行两个结点 x 和 y，表示 y 是 x 的孩子(x,y≤100)。

Outpu

第一行：树根：root。

第二行：孩子最多的结点 max。

第三行：max 的孩子。

Samples

输入数据 1

输出数据 1

4
2 
6 7 8

Limitation

1s, 1024KiB for each test case.

题解：

虽然标准答法是用二叉树，但是！我偏不用二叉树！我就要用标记数组！没错！就是那个简单到爆的标记数组！

程序：

#include<bits/stdc++.h>
using namespace std;
int m,n,f,a[110],b[210],z[110],maxn;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    	cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++)
    	z[b[i]]++;
    for(int i=1;i<=n;i++)
    	if(!z[i])
    		cout<<i<<endl;
    memset(z,0,sizeof(z));
    for(int i=1;i<=m;i++)
    	z[a[i]]++;
    for(int i=1;i<=n;i++)
		if(z[i]>=maxn)
			maxn=z[i];
	for(f=1;f<=n;f++){
		if(z[f]==maxn){
			cout<<f<<endl;
			break;
		}
	}
	for(int i=1;i<=m;i++)
		if(a[i]==f)
			cout<<b[i]<<" ";
}

原网站

版权声明
本文为[xyc20120615]所创，转载请带上原文链接，感谢
https://blog.csdn.net/xyc20120615/article/details/126243010