关于节点的度的问题，如何解决？(语言-c++)

Question

节点的度
题目描述
"节点的度"指以该节点为端点的边的条数。"偶点"指度为偶数的节点。
给你一棵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;
}

可以改一下吗？

Answer 1

• 你可以看下这个问题的回答https://ask.csdn.net/questions/356450
• 除此之外, 这篇博客: 每日一题--20200408--约瑟夫环问题：已知n个人围成一圈（编号：1，2，3，…，n），从编号为1的人开始报数，报数为m的那个人出列；从他的下一个人又从1开始数，同样报数为m的人出列；依此循环下中的 已知n个人围成一圈（编号：1，2，3，…，n），从编号为1的人开始报数，报数为m的那个人出列；从他的下一个人又从1开始数，同样报数为m的人出列；依此循环下去，直到剩余一个人。求最后这一个人在最开始的序列中编号是几号？ 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• #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]);
          }
      }
  }
  

  思路：
  其实计算机的思维很简单，只需要用最简单的描述就可以做到解决看起来很难的数学题，只要掌握题目的规律，找最简单的循环体就可以，就像数学归纳法不也是很万能的解题方式吗？

  1. 首先–>接受变量
  2. 声明一个数组来存序号（计算机的思维，零与非零）
  3. 元素就是序号，当这个被挤出去了后序号变为零，看最终剩下的最后一个元素
  4. 后面遇到零的时候就不数它
  5. 一共有n个元素，最后只剩一个
  6. 数的时候注意，因为是一个圈存的数据，数组就像是位置，位置不可以变多，绕了一圈以后要归零
  7. 最终剩下的数组元素就是我们要的序号

  不要去想着一开始的序号要存起来，出去的人连带位置一同出去，那样很麻烦

• 以下回答由chatgpt基于相关博客总结生成:

  下面是计算有根树中偶点个数的算法实现

  #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变量中。最后，判断根节点的子节点个数是否为偶数，如果是则将其计入偶点个数中。最后输出偶点个数。

Answer 2

在 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 函数来计算。

希望这些代码示例可以帮助您更好地理解节点度的计算方法。