陈洪森
(一个小陈子)
1
题目描述:
已知一棵树,有 N 个结点,编号 1 至 N,其中 1 号是根。求树的节点孩子数。
输入格式:
第一行一个整数 NN。(1≤N≤1000)(1≤N≤1000)
接下来 N 行每行 N 个 1 或 0,第 i 行第 j 列是 1,表示 i, j 两点有边,否则没有边。
输出格式:
树的节点孩子数量。
#include <bits/stdc++.h>
using namespace std;
int n,vis[1000+20];
char tre[1005][1005];
int main() {
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>tre[i][j];
}
}
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=2;j<=n;j++){
if(tre[i][j]=='1'&&!vis[j]){
cnt++;
vis[j]=1;
}
}
cout<<cnt<<" ";
}
return 0;
}
杨子阳
(杨了个阳咩~)
3
void dfs(int id,int deep) {
if(vis[] ==) {
return;
}
vis[] = 1;
for() {
if(cnt[][] && vis[] ==) {
num[]++;
dfs();
}
}
}
2 个赞
杨子阳
(杨了个阳咩~)
4
主函数
//输入
for() {
for() {
if(){
cnt[][] = 1;
cnt[][] = 1;
}
}
}
//dfs+输出
2 个赞
信友队蔡老师
(密涅瓦的猫头鹰)
8
除了i等于1的时候所有1都是子节点之外,i等于其他任何数的时候1的个数都包含一个父节点,不需要再判断访问数组
1 个赞
陈洪森
(一个小陈子)
9
#include <bits/stdc++.h>
using namespace std;
int n,vis[1000+20];
char tre[1005][1005];
int main() {
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>tre[i][j];
}
}
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if(tre[i][j]=='1'){
cnt++;
}
}
cout<<cnt<<" ";
}
return 0;
}
这样?
1 个赞
李如卉
(李如卉)
11
这样,因为与根节点右边的点肯定是他的孩子反之一个结点只会有一个父亲其他与他相连的点都是他的子节点所以只要用与它相连的点的点数减一即可
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if(tre[i][j]=='1'){
cnt++;
}
}
cout<<cnt - (i != 1)<<" ";
}
1 个赞
李如卉
(李如卉)
12
可以使用DFS但没必要因为N只有1000,还有就是帮人调代码的话尽量使用LZ的思路
1 个赞