题目链接:hdu5952-Counting Cliques
题意:
给定一个无向图,然后给定一个s,求该图中有多少个节点数为s的团。
(认真读题,比赛时以为是数圈的个数QAQ
题解:
建图:因为是无向图,答案序列1-2-3-4-5和2-3-4-5-1等价,所以由序号较小的点向序号较大的点建有向图,然后再用0-1矩阵保存原图。
直接暴搜,然后注意剪枝,因为团的定义是完全子图,所有判断一个新点是否加入团中时,要看该点与团中的所有节点之间是不是都存在边。
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,s,st,ans;
int path[15];
vector<int> edge[109];
bool mp[109][109],used[109];
void dfs(int u,int step)
{
bool flag=0;
for(int i=0; i<step; i++)
{
if(mp[u][path[i]]==0)
{
flag=1;
break;
}
}
if(flag)
return;
else
{
path[step]=u;
if(step==s-1)
{
ans++;
return;
}
}
for(int i=0; i<edge[u].size(); i++)
{
int v=edge[u][i];
if(used[v])
{
used[v]=0;
dfs(v,step+1);
used[v]=1;
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&s);
memset(mp,0,sizeof(mp));
for(int i=1; i<=n; i++)
edge[i].clear();
for(int i=1; i<=m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
mp[u][v]=mp[v][u]=1;
}
ans=0;
memset(used,1,sizeof(used));
for(int i=1; i<=n; i++)
{
used[i]=0;
dfs(i,0);
used[i]=1;
}
printf("%d\n",ans);
}
return 0;
}