节点的度
题目描述
"节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。
给你一棵n个节点的有根树，节点标号为1~n，1号节点为根节点。特别的，每个点的子节点个数不超过5。
请你输出该树中偶点的个数。
输入
第一行一个整数n。
以后n行，每行若干个整数。第i行，第一个数为mi，表示节点i的子节点个数。紧接着mi个整数，表示节点i子节点的编号。保证父节点编号小于子节点。
输出
一行一个整数，表示偶点个数。
输入 复制
3
2 2 3
0
0
输出 复制
(1(2,3))
#include<bits/stdc++.h>
using namespace std;
struct c{
int data;
c* next;
};
struct p{
int data;
c* child;
};
struct tree{
p a[100];
int n;
};
tree t;
int main()
{
cin>>t.n;
for(int i=1;i<=t.n;i++)
{
cin>>t.a[i].data;
t.a[i].child=NULL;
int cn;
cin>>cn;
if(cn!=0)
{
t.a[i].child=new c;
cin>>t.a[i].child->data;
t.a[i].child->next=NULL;
c*p=t.a[i].child;
while(cn){
c*s=new c;
cin>>s->data;
s->next=NULL;
p->next=s;
p=p->next;
cn--;
}
}
}
cout<<"1"<<endl;
for(int i=1;i<=t.n;i++){
c*k=t.a[i].child;
while(k)
{
cout<<t.a[i].data<<"."<<t.a[k->data].data<<endl;
k=k->next;
}
}
return 0;
}
可以改一下吗？
#include <stdio.h>
int main ( )
{
//1
int n,m,out = 0,count = 0;
printf("n = ");
scanf("%d",&n);
printf("m = ");
scanf("%d",&m);
//2
int a[n] ;
for (int j = 0; j < n; j++) a[j] = 1 + j;
int i = 0 ;
while(out != n -1)
{
if (a[i] != 0) {
count++;
}
if (count == m) {
count = 0;
a[i] = 0;
out++;
}
i++;
if (i == n) {
i = 0;
}
}
for (int i = 0; i < n; i++) {
if (a[i] != 0) {
printf("%d",a[i]);
}
}
}
思路：
其实计算机的思维很简单，只需要用最简单的描述就可以做到解决看起来很难的数学题，只要掌握题目的规律，找最简单的循环体就可以，就像数学归纳法不也是很万能的解题方式吗？
不要去想着一开始的序号要存起来，出去的人连带位置一同出去，那样很麻烦
下面是计算有根树中偶点个数的算法实现
#include <iostream>
#include <vector>
using namespace std;
// 定义图的节点
struct TreeNode {
int val;
vector<TreeNode*> children;
TreeNode(int v) : val(v) {}
};
// 计算有根树中的偶点个数
int countEvenPoints(TreeNode* root) {
// 如果root为空，则无偶点，直接返回0
if (!root) {
return 0;
}
int count = 0;
// 遍历树的每个节点
for (TreeNode* child : root->children) {
// 递归计算子节点中的偶点个数
count += countEvenPoints(child);
}
// 如果节点的度为偶数，则将其计入偶点个数中
if (root->children.size() % 2 == 0) {
count++;
}
return count;
}
int main() {
int n;
cin >> n;
// 创建树的节点
vector<TreeNode*> nodes(n);
for (int i = 0; i < n; i++) {
nodes[i] = new TreeNode(i+1);
}
// 建立树的连接关系
for (int i = 0; i < n; i++) {
int m;
cin >> m;
for (int j = 0; j < m; j++) {
int child;
cin >> child;
nodes[i]->children.push_back(nodes[child-1]);
}
}
// 计算有根树中的偶点个数
int answer = countEvenPoints(nodes[0]);
cout << answer << endl;
// 释放内存
for (TreeNode* node : nodes) {
delete node;
}
return 0;
}
上面的程序通过输入节点的数量、节点的子节点个数和子节点的编号来构建一棵有根树，并使用递归的方式计算了有根树中的偶点个数。程序通过定义TreeNode结构体来表示树的节点，其中包含节点的值以及子节点的指针。在countEvenPoints函数中，通过遍历节点的子节点来递归计算各子树中偶点的个数，并累加到count变量中。最后，判断根节点的子节点个数是否为偶数，如果是则将其计入偶点个数中。最后输出偶点个数。
在 C++ 中，我们可以使用邻接矩阵或邻接表来解决节点度的问题。
邻接矩阵
邻接矩阵是一个二维数组，在矩阵中的行和列坐标代表图中的节点，矩阵值表示二者之间是否有边（权重）。如果有多个节点指向同一节点，则可以将对应的矩阵值相加，最后得到的和就是该节点的度数。
以下是使用邻接矩阵计算节点度的简单代码示例：
const int MAXN = 1000; // 最多节点数
int degree[MAXN]; // 节点度数数组
// 使用邻接矩阵计算节点度数
void calcDegree(int graph[][MAXN], int n) {
memset(degree, 0, sizeof(degree)); // 初始化节点度数数组
// 遍历邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
degree[i] += graph[i][j]; // 累加每个节点的出度
}
}
}
邻接表
邻接表是一种链表数组，数组中的每个元素代表一个节点，每个节点保存一个链表，链表中存储这些节点所连接的节点。对于每个节点，其链表的长度就是该节点的度数。
以下是使用邻接表计算节点度的简单代码示例：
const int MAXN = 1000; // 最多节点数
int degree[MAXN]; // 节点度数数组
// 邻接表节点结构体
struct Node {
int v; // 相邻节点的下标
Node* next; // 链表指针
} adjList[MAXN];
// 使用邻接表计算节点度数
void calcDegree(int n) {
memset(degree, 0, sizeof(degree)); // 初始化节点度数数组
// 遍历邻接表
for (int i = 0; i < n; i++) {
Node* p = adjList[i].next;
while (p) {
degree[i]++; // 累加每个节点的出度
degree[p->v]++; // 累加每个节点的入度
p = p->next;
}
}
}
希望这些代码示例可以帮助您解决节点度的问题。
另外，如果您希望使用现成的库来计算节点度，可以尝试使用 Boost C++ 库，其中包含了图论相关的功能。
以下是使用 Boost C++ 库计算节点度的简单代码示例：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS> Graph;
// 使用 Boost 库计算节点度数
void calcDegree(const Graph& graph, int n) {
std::vector<int> degree(n, 0); // 初始化节点度数数组
// 遍历图中的每个节点
for (int i = 0; i < n; i++) {
degree[i] = boost::out_degree(i, graph); // 计算节点的出度
}
}
这里的 Graph 类型表示使用邻接表存储的无向图。通过 boost::out_degree 函数可以计算某个节点的出度，进度可以使用 boost::in_degree 函数来计算。
希望这些代码示例可以帮助您更好地理解节点度的计算方法。