Counting Cliques (优雅爆搜)
Sample Input
3
4 3 2
1 2
2 3
3 4
5 9 3
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
6 15 4
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
Sample Output
3
7
15
这道题就是给了n个点,m条边,然后看里面有几个完全图。
就是爆搜。。
但是比赛的时候不知道怎么搞,觉得自己的想法肯定炸,还是纪大佬优秀啊!
思路就是加一个点进去,就要看这个点跟其他点是否有连边,如果有一条边没有那么这个边就不是完全图里的。用a数组记录一下目前选了哪几个在完全图里的。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long
#define mod 1000000007
#define INF 1e9
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
bool edge[200][200];
vector<int> vec[200];
int a[200];
int n,m,s,res;
void dfs(int num,int u)
{
if(num==s)
{
res++;
return;
}
int vecn=vec[u].size();
for(int i=0;i<vecn;i++)
{
bool flag=1;
for(int j=0;j<num;j++)
{
if(!edge[vec[u][i]][a[j]])
flag=0;
}
if(flag)
{
//cout<<num<<endl;
a[num]=vec[u][i];
dfs(num+1,vec[u][i]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
mem(a,0);
mem(edge,0);
int i;
for(i=0;i<200;i++)
{
vec[i].clear();
}
cin>>n>>m>>s;
for(i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
if(u>v)
{
swap(u,v);
}
vec[u].push_back(v);
edge[u][v]=1;edge[v][u]=1;
}
res=0;
for(i=1;i<=n;i++)
{
a[0]=i;
dfs(1,i);
}
cout<<res<<endl;
}
}