数据过水
查看原帖
数据过水
879904
WorldMachine楼主2024/4/17 11:40

下面的代码没有把两个节点的度数都增加。但是过了,跑得飞快。

#include <bits/stdc++.h>
using namespace std;
void qread(int &a) {
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') a = a * 10 - '0' + c, c = getchar();
}
const int MAXN = 100005, MAXM = 200005;
int n, m, deg[MAXN], u[MAXM], v[MAXM], vis[MAXN], ans;
vector<int> G[MAXN];
int main() {
	qread(n), qread(m);
	for (int i = 1; i <= m; i++) {
		qread(u[i]), qread(v[i]);
		deg[u[i]]++, deg[v[i]];
	}
	for (int i = 1; i <= m; i++) {
		if (deg[u[i]] > deg[v[i]] || deg[u[i]] == deg[v[i]] && u[i] > v[i]) swap(u[i], v[i]);
		G[u[i]].push_back(v[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int u : G[i]) vis[u] = i;
		for (int u : G[i]) {
			for (int v : G[u]) ans += vis[v] == i;
		}
	}
	printf("%d", ans);
}
2024/4/17 11:40
加载中...