用的 O(n2) 的hash方法。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<bitset> using namespace std; typedef unsigned long long LL; int m; int fa[52]; int n; vector<int> g[1100]; struct node { LL value; int id; }a[1100]; int cmp(node a,node b) { if (a.value!=b.value) return a.value<b.value; return a.id<b.id; } int ans[11000]; LL v[11000]; vector<LL> tmp; vector<int> ttmp; void dfs(int x,int fa) { v[x]=31; for (int i=0;i<g[x].size();i++) if (g[x][i]!=fa) dfs(g[x][i],x); tmp.clear(); for (int i=0;i<g[x].size();i++) if (g[x][i]!=fa) tmp.push_back(v[g[x][i]]); sort(tmp.begin(),tmp.end()); for (int i=0;i<tmp.size();i++) v[x]=v[x]*37LL+tmp[i]; } int main() { scanf("%d",&m); for (int j=1;j<=m;j++) { scanf("%d",&n); for (int i=1;i<=n;i++) g[i].clear(); int root; for (int i=1;i<=n;i++) { int x; scanf("%d",&x); if (x==0) continue; else g[x].push_back(i),g[i].push_back(x); } ttmp.clear(); for (int i=1;i<=n;i++) dfs(i,0),ttmp.push_back(v[i]); sort(ttmp.begin(),ttmp.end()); for (int i=0;i<ttmp.size();i++) a[j].value=a[j].value*221LL+ttmp[i]; a[j].id=j; } sort(a+1,a+1+m,cmp); for (int i=1;i<=m;i++) if (a[i].value!=a[i-1].value) ans[a[i].id]=a[i].id; else ans[a[i].id]=ans[a[i-1].id]; for (int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }