Counting Cliques

题意：给你n个点，m条边，求大小为s(s<=10)的团有多少个，每个点的度最多20。

看到数据这么小，想着各种bitset暴力，想着把3元团预处理，再预处理4元团等等。写了两个多小时发现复杂度算错了，9元团的个数能达到1e6，这样我们两层循环预处理就不行了。

看题解原来是ssssb的爆搜，题目给你degree<=20就是在暗示你可以爆搜，于是爆搜写了一发结果TLE，What f*ck。再加了个小小的优化然后AC。。

TLE代码：

int n,m,s,sum;
int vis[101],g[101][101];
int tot,head[101];
struct egde
{int to,next;
} e[N];
void add(int u,int v)
{e[tot].to=v,e[tot].next=head[u];head[u]=tot++;
}
void solve(int u,int num)
{if(num==s){sum++;return ;}for(int i=head[u];i+1;i=e[i].next){int v=e[i].to,flag=1;if(vis[v]) continue;for(int i=1;i<=n;i++) if(vis[i]&&!g[v][i]) flag=0;if(flag){vis[v]=1;solve(v,num+1);vis[v]=0;}}
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&s);memset(vis,0,sizeof(vis));memset(g,0,sizeof(g));int u,v;tot=sum=0;memset(head,-1,sizeof(head));for(int i=1; i<=m; i++)//建单向边减少搜索次数{scanf("%d%d",&u,&v);if(u>v) swap(u,v);add(u,v);g[v][u]=g[u][v]=1;}for(int i=1; i<=n; i++)if(!vis[i]){vis[i]=1;solve(i,1);
//            vis[i]=0;}printf("%d\n",sum);}return 0;
}

上面的solve里面每次都要验证100个点，这样复杂度是100*10*100*100*T。

把这个地方优化一下， 把已标记过的放入栈里，每次判10个就可以了。

int n,m,s,sum;
int vis[101],g[101][101],Stack[101];
int tot,head[101];
struct egde
{int to,next;
} e[N];
void add(int u,int v)
{e[tot].to=v,e[tot].next=head[u];head[u]=tot++;
}
void solve(int u,int num)
{if(num==s){sum++;return ;}for(int i=head[u];i+1;i=e[i].next){int v=e[i].to,flag=1;for(int j=1;j<=num&&flag;j++) if(!g[v][Stack[j]]) flag=0;if(flag){Stack[num+1]=v;solve(v,num+1);}}
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&s);memset(g,0,sizeof(g));int u,v;tot=sum=0;memset(head,-1,sizeof(head));for(int i=1; i<=m; i++)//建单向边减少搜索次数{scanf("%d%d",&u,&v);add(u,v);g[v][u]=g[u][v]=1;}for(int i=1; i<=n; i++){Stack[1]=i;solve(i,1);}printf("%d\n",sum);}return 0;
}