bzoj4264

哈希

cf原题。。。没见过的话真想不出来

将邻接表排序哈希，判断是否相同，但是会漏掉两点相邻的情况，于是再把自己加入自己的邻接表，然后再哈希判断。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
vector<int> G[N];
int n, m; 
ll ans;
map<ll, ll> mp; 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i) 
    {       
        sort(G[i].begin(), G[i].end());
        G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
        ll Hash = 0;
        for(int j = 0; j < G[i].size(); ++j)
            Hash = Hash * 1234567ll + G[i][j];
        ++mp[Hash];
    }   
    for(int i = 1; i <= n; ++i)
    {
        G[i].push_back(i);
        sort(G[i].begin(), G[i].end());
        G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
        ll Hash = 0;
        for(int j = 0; j < G[i].size(); ++j)
            Hash = Hash * 1234567ll + G[i][j];
        ++mp[Hash];
    }
    for(map<ll, ll> :: iterator it = mp.begin(); it != mp.end(); ++it)
        ans += (it -> second) * (it -> second - 1ll) / 2ll;
    printf("%lld
", ans);   
    return 0;
}