本文最后更新于 184 天前,其中的信息可能已经有所发展或是发生改变。
本文代码严格按照Linux C++标准编写,空格、缩进符合标准。
1.[GESP202403 七级] 交流问题
#include<bits/stdc++.h> const int N = 1e6 + 10; using namespace std; vector <int> aa[N]; bool bb[N]; int calc_mxd() { int k = 0, f = 1; char c = getchar(); while (c < '0' or c > '9') { if (c == '-') { f = -1; } c = getchar(); } while (c >= '0' and c <= '9') { k = k * 10 + c - '0'; c = getchar(); } return k * f; } void output_mxd(int x) { if (x < 0) { putchar('-'); x = -x; } if (x < 10) { putchar(x + '0'); } else { output_mxd(x / 10); putchar(x % 10 + '0'); } } void dfs(int u, int &t1, int &t2, bool f) { bb[u] = true; if (f) { t1++; } else { t2++; } for (int v : aa[u]) { if (!bb[v]) { dfs(v, t1, t2, !f); } } } int main() { int n = calc_mxd(), m = calc_mxd(); while (m--) { int u = calc_mxd(); int v = calc_mxd(); aa[u].push_back(v); aa[v].push_back(u); } int t1 = 0, t2 = 0; for (int i = 1; i <= n; i++) { if (!bb[i]) { int a = 0; int b = 0; dfs(i, a, b, true); t1 += min(a, b), t2 += max(a, b); } } output_mxd(t1), putchar(' '), output_mxd(t2); return 0; }