题目分析
【ACM_HDU|HDU 5952 Counting Cliques(2016ACM/ICPC亚洲区沈阳站-重现赛)】这道题看样子没有什么办法，主要就是有策略的暴力，因为每个点连接的点不超过20个，那么就可以直接进行暴力，但是这样会有很多重复，因此需要剪枝，具体情况就是每次搜过一个点之后就把这个点连接的所有边都删除，这样就跑的很快了。。
文章图片
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 105;
int vis[maxn][maxn], degree[maxn], Stack[maxn], h, c;
int ans;
int T, N, M, S;
vector vec[maxn];
void dfs(int u, int flag){
if(h == S){
ans++;
return;
}
if((vec[u].size()-flag) < (S-h) || flag >= vec[u].size()) return ;
int cnt = 0;
for(int i = 0;
i < h;
i++)
if(!vis[vec[u][flag]][Stack[i]]){ cnt = 1;
break;
}
if(!cnt){
Stack[h++] = vec[u][flag];
dfs(u, flag+1);
h--;
}
dfs(u, flag+1);
}void init(){
memset(Stack, 0, sizeof(Stack));
memset(degree, 0, sizeof(degree));
memset(vis, 0, sizeof(vis));
for(int i = 0;
i < maxn;
i++)
vec[i].clear();
}int main(){
scanf("%d", &T);
while(T--){
init();
scanf("%d%d%d", &N, &M, &S);
int u, v;
for(int i = 0;
i < M;
i++){
scanf("%d%d", &u, &v);
vis[u][v] = vis[v][u] = 1;
vec[u].push_back(v);
vec[v].push_back(u);
degree[u]++;
degree[v]++;
}
ans = 0;
for(int i = 1;
i <= N;
i++){
if(degree[i] < S-1) continue;
//剪枝
h = 0;
Stack[h++] = i;
dfs(i, 0);
for(int j = 1;
j <= N;
j++){//剪枝
if(vis[i][j]){
degree[j]--;
vis[i][j] = vis[j][i] = 0;
}
}
}
printf("%d\n", ans);
}
return 0;
}
