hdu 5952 Counting Cliques(dfs+剪枝/求指定大小团的个数)

题目

n(n<=100)个点，m(m<=1e3)条双向边，

保证点最大的度数不超过20（不知道有啥用，照顾时限叭）

求恰为s(2<=s<=10)大小的团的个数

团即为一个点集，该点集中的点两两之间都有边，又称完全图

思路来源

https://www.cnblogs.com/kkkkahlua/p/7704245.html

题解

暴搜，要加入一个点的时候，判断是否和当前搜索路径内的所有点之间都有边，是才加入

剪枝，主要是调整了搜索顺序，使得建图的时候，只有小的点向大的点之间连边

这样，一个大小为n的团只会被检查一次，而不是次

剪枝复杂度较为玄学，但增序搜索使点集呈增序排列降复杂度这一点，毋庸置疑

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int maxm=1e3+5;
typedef pair<int,int> P;
int t,n,m,s;
int u,v;
int mp[maxn][maxn];
int step[15],ans;
vector<int>E[maxn];
bool flag; 
void dfs(int now,int u)
{
	step[now]=u;
	if(now==s)
	{
		ans++;
		return;
	}
	for(int i=0;i<E[u].size();++i)
	{
		int v=E[u][i];
		flag=1;
		for(int j=1;j<=now&&flag;++j)
		if(!mp[step[j]][v])flag=0;
		if(!flag)continue;
		dfs(now+1,v);
	}
}
void work()
{
	ans=0;
	memset(mp,0,sizeof mp);
	for(int i=1;i<=n;++i)
	E[i].clear();
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&u,&v);
		if(u>v)swap(u,v);
		mp[u][v]=1;
		E[u].push_back(v);
	}
	for(int i=1;i<=n;++i)
	dfs(1,i);
	printf("%d\n",ans);
}
int main()
{
	scanf("%d",&t);
	while(t--)work();
	return 0;
}