专栏文章

图-度的数量

__Manstein_
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miql1s1s
此快照首次捕获于
2025/12/04 06:32
3 个月前
此快照最后确认于
2025/12/04 06:32
3 个月前
查看原文

图 - 度的数量

*问题描述

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

解释：

1.对于无向图 G=(V,E)G=(V,E) ，顶点 vv 的度记为 degree(v)degree(v) ，表示与顶点 vv 直接相连的边的数量。
2.自环（如果有）会对度贡献 2，因为自环同时连接到同一个顶点。

输入格式：

第一行输入两个正整数 n,mn,m ，表示图中有 nn 个点与 mm 条边。
接下来 mm 行，每行输入 2 个正整数 a,ba,b ，表示 a,ba,b 之间有一条无向边。
(1≤n≤105,1≤m≤2×105,1≤a,b≤n)(1≤n≤10^ 5 ,1≤m≤2×10^ 5 ,1≤a,b≤n)

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...