救救吧树节点孩子数80分

题目描述:

已知一棵树,有 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;
}

这题不是要用电风扇吗

2 个赞
void dfs(int id,int deep) {
	if(vis[] ==) {
		return;
	}
	vis[] = 1;
	for() {
		if(cnt[][] && vis[] ==) {
			num[]++;
			dfs();
		}
	}
}
2 个赞

主函数

//输入
for() {
	for() {
		if(){
			cnt[][] = 1;
			cnt[][] = 1;
		}
	}
}
//dfs+输出
2 个赞

要啥dfs…

1 个赞

你干嘛要j从第二个开始?假定1是根节点?

1 个赞

不然?

1 个赞

除了i等于1的时候所有1都是子节点之外,i等于其他任何数的时候1的个数都包含一个父节点,不需要再判断访问数组

1 个赞
#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 个赞

:sweat::sweat::sweat:

2 个赞

这样,因为与根节点右边的点肯定是他的孩子反之一个结点只会有一个父亲其他与他相连的点都是他的子节点所以只要用与它相连的点的点数减一即可

	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 个赞

可以使用DFS但没必要因为N只有1000,还有就是帮人调代码的话尽量使用LZ的思路

1 个赞

不要提供AC代码

2 个赞

sorry,我不知道水论坛没几天