暴力姿势永远学不会的姿势

先说题意：n点m条边，问图中有多少种情况是：有s个点两两相连（问子图的独立团，其中点数为s）

看到数据量其实并不大，n是100，m是1000，s最大为10

还有一句话：It is guaranteed that the maximum degree of the vertices is no larger than 20.

这句话其实是提示了最好的枚举方向的：从小到大来枚举，当前团中的最小编号

用mp【u】【v】来存储边，用O（1）的时间来确定u和v是否相连

用vec【i】来存储边，可以直接枚举与点i相邻的所有边

当然，这样交上去是TLE的

剪枝条件1：记录每个点的度数。如果点i的度数+当前选中的所有点数+1仍然小于s，那么不需要搜索了

然后，还是TLE

学到的剪枝方法：对vec【i】中的点进行排序：为什么？因为这样，在dfs中就可以按照顺序从小到大进行搜索

如果不排序，那么每次都要从0枚举到vec【i】-1，是很浪费时间的

剪枝条件2：如果当前size中的值全部选出来都不够，那么及时return

剪枝条件3：起点的最大值为：n-s+1（意味着最大的s个编号的值全部相连，是1种情况，n-s+2这个点是不可能作为起点的，因为之后点数不够）

按照这个思路写出来的代码在时限上就足够了

</pre><pre name="code" class="cpp">#include<bits/stdc++.h>
using namespace std;const int maxn=110;
int T,n,m,s;
int cnt[maxn];
int mp[maxn][maxn];
vector<int> vec[maxn];
int ans,sz,st;
int num[maxn];void dfs(int pos,int step){if (step>s){ans++;//for(int i=1;i<=s;i++)//    printf("%d%c",num[i],i==s?'\n':' ');return;}for(int x=pos;x<sz-(s-step);x++){int v=vec[st][x];if (cnt[v]+step<s) continue;if (v<st) continue;int i;for(i=1;i<step;i++)if (!mp[num[i]][v]) break;if (i==step){num[step]=v;dfs(x+1,step+1);}}
}int main(){//freopen("input.txt","r",stdin);int u,v;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) mp[i][j]=0;cnt[i]=0;vec[i].clear();}while(m--){scanf("%d%d",&u,&v);cnt[u]++;cnt[v]++;vec[u].push_back(v);vec[v].push_back(u);mp[u][v]=mp[v][u]=1;}ans=0;int End=n-s+1;for(int i=1;i<=End;i++)if (cnt[i]+1>=s){num[1]=st=i;sort(vec[i].begin(),vec[i].end());sz=vec[i].size();dfs(0,2);}printf("%d\n",ans);}return 0;
}