和题解写的很像,但怎么改都不行,请各路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;
}