图-度的数量

· · 算法·理论

图 - 度的数量

*问题描述

给定一张具有 n 个点 m 条边的无向图，你需要输出每个点的度是多少。

解释：

1.对于无向图 G=(V,E) ，顶点 v 的度记为 degree(v) ，表示与顶点 v 直接相连的边的数量。

2.自环（如果有）会对度贡献 2，因为自环同时连接到同一个顶点。

输入格式：

第一行输入两个正整数 n,m ，表示图中有 n 个点与 m 条边。

接下来 m 行，每行输入 2 个正整数 a,b ，表示 a,b 之间有一条无向边。

5 ,1≤m≤2×10^ 5 ,1≤a,b≤n)

代码

#include <iostream>
#include <cmath>
#include <string>
#include <cstdio>
#include <vector>//头文件
using namespace std;
typedef pair<int, int> er;
vector <er>g[500005];//邻接表
void add(int a, int b, int c) {
    g[a].push_back({ c,b });
}//两点之间有权为c的边
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;

        add(x, y, 1);
        add(y, x, 1);//无向图
    }
    for (int i = 1; i <= n; i++) {
        cout << g[i].size() << " ";//输出长度
    }

    return 0;
}