传送门：https://codeforces.com/problemset/problem/154/C
求出无向图中，满足所有出边都相连或出边直接连接点对的点对数。很显然可以暴力枚举点对一对对去check，时间复杂度\(O(n^2+m)\)。
#include <bits/stdc++.h>using namespace std;inline int read() {char c;bool flag = false;while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;int res = c - '0';while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';return flag ? -res : res;
}const int N = 2e5 + 1;int head[N], cnt, ans;
struct Edge {int v, next;
} e[N];void add(int u, int v) {e[cnt].v = v;e[cnt].next = head[u];head[u] = cnt++;
}map<pair<int, int>, int> mp;bool check(int x, int y) {for (int i = head[x]; ~i; i = e[i].next) {int to = e[i].v;if (to != y && !mp[make_pair(to, y)] && !mp[make_pair(y, to)]) return false;}for (int i = head[y]; ~i; i = e[i].next) {int to = e[i].v;if (to != x && !mp[make_pair(to, x)] && !mp[make_pair(x, to)]) return false;}return true;
}int main() {memset(head, -1, sizeof head);int n = read(), m = read();for (int i = 1; i <= m; ++i) {int u = read(), v = read();add(u, v);add(v, u);mp[make_pair(u, v)] = 1;}for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) if (check(i, j)) ++ans;printf("%d", ans);return 0;
}
考虑优化，枚举点对肯定不可行，如何快速判定两点出边抵达的点相同？我们不妨把点集看作一个数，这样就能通过排序快速计算点集相同的点对，这里可以同行集合哈希来实现，分有边直连的点对和无边直连的点对两种情况计数即可。时间复杂度\(O(nlog_{2}n)\)，瓶颈在于排序。
#include <bits/stdc++.h>typedef unsigned long long ull;
using namespace std;inline int read() {char c;bool flag = false;while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;int res = c - '0';while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';return flag ? -res : res;
}const int N = 1e6 + 1;ull p[N], hs[N];int u[N], v[N];int main() {int n = read(), m = read();p[0] = 1;for (int i = 1; i <= n; ++i) p[i] = p[i - 1] * 13;for (int i = 1; i <= m; ++i) {u[i] = read(), v[i] = read();hs[u[i]] += p[v[i]];hs[v[i]] += p[u[i]];}long long ans = 0;for (int i = 1; i <= m; ++i) if (hs[u[i]] + p[u[i]] == hs[v[i]] + p[v[i]]) ++ans;sort(hs + 1, hs + n + 1);int cnt = 1;for (int i = 2; i <= n; ++i) {if (hs[i] == hs[i - 1]) ++cnt;else {ans += 1ll * cnt * (cnt - 1) / 2;cnt = 1;}}ans += 1ll * cnt * (cnt - 1) / 2;printf("%lld", ans);return 0;
}
