hash大法好
#include#include #include #include #include #include #include #define ll long long#define N 1000006#define M 2000006using namespace std;using std::vector;inline int read(){ int ret=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while ('0'<=ch&&ch<='9'){ ret=ret*10-48+ch; ch=getchar(); } return ret;}vector e[N];int n,m;struct Hash{ int k,P; int hash[N]; Hash(){} void load(){ memset(hash,0,sizeof(hash)); for (int i=1;i<=n;++i) for (int j=0;j a[N];ll ans;void renew_ans(){ for (int i=1;i<=n;++i) a[i]=make_pair(h0.hash[i],h1.hash[i]); sort(a+1,a+n+1); int cnt=0; for (int i=1;i<=n;++i){ ++cnt; if (i==n||a[i]!=a[i+1]){ ans+=(ll)cnt*(cnt-1)/2; cnt=0; } }}int main(){ h0.k=23;h0.P=2333333; h1.k=233;h1.P=1000000007; n=read();m=read(); for (int i=1;i<=m;++i){ int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); } ans=0; for (int k=0;k<2;++k){ for (int i=1;i<=n;++i) sort(e[i].begin(),e[i].end()); h0.load();h1.load(); renew_ans(); for (int i=1;i<=n;++i) e[i].push_back(i); } printf("%lld\n",ans); return 0;}