60pts求调(7,8,9,10TLE)
查看原帖
60pts求调(7,8,9,10TLE)
1144913
guchenxi16楼主2025/7/31 12:29

和题解写的很像,但怎么改都不行,请各路dalao帮帮忙。(跪拜跪拜)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
long long n, m, head[N], Next[N], to[N], cnt, sum, pos1, pos2;
bool check[N];
inline void add(long long x, long long y) {
	cnt++;
	to[cnt] = y;
	Next[cnt] = head[x];
	head[x] = cnt;
}
inline void dfs(long long x, long long y) {
	y == 1 ? pos1++ : pos2++;
	for (int i = head[x]; i != -1; i = Next[i])
		if (!check[to[i]]) {
			check[to[i]] = 1;
			dfs(to[i], !y);
		}
}
int main() {
	memset(head, -1, sizeof(head));
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= m; i++) {
		long long a, b;
		scanf("%lld%lld", &a, &b);
		add(a, b);
		add(b, a);
	}
	for (int i = 1; i <= n; i++)
		if (!check[i]) {
			check[i] = 1;
			pos1 = 0;
			pos2 = 0;
			dfs(i, 0);
			sum += max(pos1, pos2);
		}
	printf("%lld %lld", n - sum, sum);
	return 0;
}
2025/7/31 12:29
加载中...