统计图的度的c++代码

下面是一个简单的 C++ 代码，用于统计一个图的每个节点的度数：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数

    vector<int> degree(n, 0); // 存储每个节点的度数

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点

        degree[u]++; // 两个节点的度数都加1
        degree[v]++;
    }

    for (int i = 0; i < n; i++) {
        cout << "Node " << i << " has degree " << degree[i] << endl;
    }

    return 0;
}

该代码通过一个 `vector` 数组来存储每个节点的度数，遍历每条边，将连接的两个节点的度数都加1，最后输出每个节点的度数。

相关问题

统计度为1结点的个数的C++代码

### 回答1：
以下是统计度为1结点个数的C++代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

int head[N], ver[N], nxt[N], cnt;
bool vis[N]; // 标记结点是否被遍历过

void add(int x, int y) // 添加一条边
{
    ver[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

int dfs(int u) // 深度优先搜索
{
    vis[u] = true;
    int res = 0;
    for (int i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (!vis[v]) // 如果v结点没有被遍历过
        {
            int tmp = dfs(v);
            if (tmp == 1) res++; // 如果v结点是度为1的结点，则res加1
        }
    }
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i]) // 如果i结点没有被遍历过
        {
            int tmp = dfs(i);
            if (tmp == 1) ans++; // 如果i结点是度为1的结点，则ans加1
        }
    }
    cout << ans << endl;
    return 0;
}

该代码使用深度优先搜索遍历整张图，如果当前结点的度为1，则计数器加1。最后输出计数器的值即可。

### 回答2：
统计度为1结点的个数的C代码如下：

#include <stdio.h>
#include <stdlib.h>

// 定义树的结点结构体
struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 创建新结点的函数
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 统计度为1结点的个数的函数
int countNodesWithDegreeOne(struct TreeNode* root) {
    // 如果结点为空，返回0
    if (root == NULL) {
        return 0;
    }

    // 如果结点的左右子树为空，表示该结点是度为1的结点，返回1
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    // 统计左子树和右子树中度为1结点的个数
    int leftCount = countNodesWithDegreeOne(root->left);
    int rightCount = countNodesWithDegreeOne(root->right);

    // 返回左右子树中度为1结点的个数之和
    return leftCount + rightCount;
}

int main() {
    // 创建一棵树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(4);
    root->right->left = createNode(5);

    // 统计度为1结点的个数
    int count = countNodesWithDegreeOne(root);
    printf("度为1的结点的个数为：%d\n", count);

    return 0;
}

代码的思路是通过递归的方式遍历二叉树的每个结点，如果一个结点的左右子树都为空，则该结点是度为1的结点，递归地统计左子树和右子树中度为1结点的个数，并将二者之和返回。最后输出度为1结点的个数。

### 回答3：
统计度为1的节点个数的C代码如下：

#include <stdio.h>
#include <stdlib.h>

// 树节点结构体
typedef struct TreeNode {
    int data;                  // 节点数据
    struct TreeNode* left;     // 左子节点指针
    struct TreeNode* right;    // 右子节点指针
} TreeNode;

// 统计度为1的节点个数函数
int countDegreeOne(TreeNode* root){
    if(root == NULL)  // 如果树为空树，则返回0
        return 0;
    else if(root->left == NULL && root->right != NULL)  // 如果只有右子节点或只有左子节点，则返回1
        return 1;
    else if(root->left != NULL && root->right == NULL)
        return 1;
    else  // 递归地统计左子树和右子树中度为1的节点个数，再加上根节点是否为度为1的节点
        return countDegreeOne(root->left) + countDegreeOne(root->right) + ((root->left != NULL && root->right != NULL) ? 0 : 1);
}

int main() {
    // 创建一个测试用的二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
    
    root->data = 1;
    node1->data = 2;
    node2->data = 3;
    node3->data = 4;
    
    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node1->right = NULL;
    node2->left = NULL;
    node2->right = NULL;
    node3->left = NULL;
    node3->right = NULL;
    
    // 调用函数统计度为1的节点个数
    int count = countDegreeOne(root);
    printf("度为1的节点个数为：%d\n", count);
    
    // 释放内存
    free(root);
    free(node1);
    free(node2);
    free(node3);
    
    return 0;
}

这段代码中，首先定义了树节点的结构体，并且定义了一个统计度为1的节点个数的函数`countDegreeOne`。在该函数中，通过递归的方式来统计左子树和右子树中度为1的节点个数，并将其累加。对于当前节点，若只存在左子节点或只存在右子节点，则返回1，表示该节点为度为1的节点。最后，在主函数`main`中，创建了一个测试用的二叉树，并调用函数`countDegreeOne`来统计度为1的节点的个数，并输出结果。最后释放了动态分配的内存。

图的度序列C++算法

图的度序列指的是图中每个节点的度数（即与该节点相连的边数）构成的序列，可以用来研究图的结构和性质。下面是一段实现度序列的 C++ 代码：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;

int n, m; // n 表示节点数，m 表示边数
vector<int> G[MAXN]; // 存储图的邻接表
int deg[MAXN]; // 存储每个节点的度数

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        deg[i] = G[i].size();
    }
    for (int i = 1; i <= n; i++) {
        cout << deg[i] << " ";
    }
    cout << endl;
    return 0;
}

首先读入节点数和边数，接着读入每条边的两个端点，并将它们加入对应节点的邻接表中。在这个过程中，我们可以顺便计算出每个节点的度数。最后遍历一遍所有节点，输出它们的度数即可。

需要注意的是，由于这个算法使用了邻接表存储图，所以时间复杂度为 $O(m+n)$，其中 $m$ 表示边数，$n$ 表示节点数。如果使用邻接矩阵存储图，则时间复杂度为 $O(n^2)$，因为需要遍历整个邻接矩阵统计每个节点的度数。