设$f[i][j][k]$表示从房间$j$的第$k$扇门进去探索不超过$i$步的情况。
对于$0$步的情况,可以用每个房间的度数来表示。
否则可以绕着那个房间走一圈,将所有情况依次hash来表示。
最后对于每个房间求出$f$的最小表示,即可完成hash。
时间复杂度$O(n^4)$。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const int N=105;
int n,m,i,j,k,t,o,x,d[N],a[N][N],b[N][N],q[N];ll f[2][N][N];
vector<ll>g[N];vector<int>ans[N];
inline bool cmp(int x,int y){return g[x]==g[y]?x<y:g[x]<g[y];}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&d[i]);
for(j=1;j<=d[i];j++)scanf("%d",&a[i][j]),b[i][a[i][j]]=j;
}
for(i=1;i<=n;i++)for(j=1;j<=d[i];j++)f[0][i][j]=d[i]+1;
for(i=1;i<=n;i++){
o^=1;
for(j=1;j<=n;j++)for(k=1;k<=d[j];k++){
f[o][j][k]=f[o^1][j][k]*10007+13331;
x=a[j][k];
for(t=b[x][j];t<=d[x];t++)f[o][j][k]=f[o][j][k]*233+f[o^1][x][t];
for(t=1;t<b[x][j];t++)f[o][j][k]=f[o][j][k]*233+f[o^1][x][t];
}
}
for(i=1;i<=n;i++){
for(j=1;j<=d[i];j++)g[i].push_back(f[o][i][j]);
for(j=2;j<=d[i];j++){
vector<ll>h;
for(k=j;k<=d[i];k++)h.push_back(f[o][i][k]);
for(k=1;k<j;k++)h.push_back(f[o][i][k]);
g[i]=max(g[i],h);
}
g[i].push_back(d[i]);
q[i]=i;
}
sort(q+1,q+n+1,cmp);
for(i=1;i<=n;i=j){
for(j=i;j<=n&&g[q[i]]==g[q[j]];j++);
if(i+1==j)continue;
for(m++,k=i;k<j;k++)ans[m].push_back(q[k]);
}
if(!m)puts("none");
else{
sort(ans+1,ans+m+1);
for(i=1;i<=m;i++){
printf("%d",ans[i][0]);
for(j=1;j<ans[i].size();j++)printf(" %d",ans[i][j]);
puts("");
}
}
return 0;
}