Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <map>
- using namespace std;
- const long long MOD = 1442501923, MOD2 = 2556975823;
- const long long p = 1337057, p2 = 1216091;
- int main() {
- int n, m;
- cin >> n >> m;
- vector<vector<int>> g(n + 1), gg(n + 1);
- for (int i = 0; i < m; ++i) {
- int v, u;
- cin >> v >> u;
- g[v].push_back(u);
- gg[v].push_back(u);
- g[u].push_back(v);
- gg[u].push_back(v);
- }
- for (int i = 1; i <= n; ++i) {
- gg[i].push_back(i);
- sort(g[i].begin(), g[i].end());
- sort(gg[i].begin(), gg[i].end());
- }
- vector<long long> h, hh, h2, hh2;
- for (int i = 1; i <= n; ++i) {
- long long hs = 0LL, hs2 = 0LL;
- long long pow = 1LL, pow2 = 1LL;
- for (int j: g[i]) {
- hs = (hs + (long long)(j) * pow) % MOD;
- hs2 = (hs2 + (long long)(j) * pow2) % MOD2;
- pow = (pow * p) % MOD;
- pow2 = (pow2 * p2) % MOD2;
- }
- h.push_back(hs);
- h2.push_back(hs2);
- hs = 0LL;
- pow = 1LL;
- hs2 = 0LL;
- pow2 = 1LL;
- for (int j: gg[i]) {
- hs = (hs + (long long)(j) * pow) % MOD;
- hs2 = (hs2 + (long long)(j) * pow2) % MOD2;
- pow = (pow * p) % MOD;
- pow2 = (pow2 * p2) % MOD2;
- }
- hh.push_back(hs);
- hh2.push_back(hs2);
- }
- sort(h.begin(), h.end());
- sort(hh.begin(), hh.end());
- sort(h2.begin(), h2.end());
- sort(hh2.begin(), hh2.end());
- h.push_back(-1);
- hh.push_back(-1);
- h2.push_back(-1);
- hh2.push_back(-1);
- long long ans = 0LL;
- int prev = 0;
- for (int i = 1; i < n + 1; ++i) {
- if (h[i] != h[prev] || h2[i] != h2[prev]) {
- ans += (long long)(i - prev) * (long long)(i - prev - 1) / 2LL;
- prev = i;
- }
- }
- prev = 0;
- for (int i = 1; i < n + 1; ++i) {
- if (hh[i] != hh[prev] || hh2[i] != hh2[prev]) {
- ans += (long long)(i - prev) * (long long)(i - prev - 1) / 2LL;
- prev = i;
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement