hdu5952:Counting Cliques-求图中指定大小的团的个数-暴搜

(有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

目录

题意:传送门

 原题目描述在最下面。
 给你n个点m条边的无向图,求指定大小的团的个数。

思路:

  • 十分详细易懂的讲解:传送门
  • 暴搜(真的很暴力吗?)。就是再搜索的时候判断当前点是不是和之前的点都连通。
  • 然后一个团只需要搜到一次就够了。所以这位大佬的一个剪枝就是确保下一个搜到点的编号大于当前节点,然后建图的时候都是小点指向大点。

AC代码:

#include <bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))  
#define fuck(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int INF = 0x3f3f3f3f;
const int N = 1e2 + 7;
int n, m, q;
int mp[N][N];
int stak[N];
struct lp{
  int u,v,nex;
}cw[N*N];
int head[N],tot,ans;
void add(int u,int v){
  cw[++tot].u=u;cw[tot].v=v;cw[tot].nex=head[u];
  head[u]=tot;
  /*cw[++tot].u=v;cw[tot].v=u;cw[tot].nex=head[v];
  head[v]=tot;*/
}
bool check(int u,int top){
  for(int i=0;i<=top;++i){
    if(!mp[stak[i]][u])return false;
  }
  return true;
}
void dfs(int u,int top,int fa){
  stak[top]=u;
  if(top==q-1){
    ++ans;--top;return;
  }
  for(int i=head[u];~i;i=cw[i].nex){
    int v = cw[i].v;
    //if(v==fa)continue;
    if(check(v,top)){
      dfs(v,top+1,u);
    }
  }
}
int main(){
  int tim,tc = 0;
  scanf("%d", &tim);
  while(tim--){
    scanf("%d%d%d",&n,&m,&q);
    ans=0;tot=-1;
    memset(mp,0,sizeof(mp));
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;++i){
      int u,v;
      scanf("%d%d",&u,&v);
      if(u>v)swap(u,v);
      add(u,v);
      mp[u][v]=1;
      //mp[v][u]=1;
    }
    for(int i=1;i<=n;++i){
      dfs(i,0,-1);
    }
    printf("%d\n", ans);
  }
  return 0;
}


这里写图片描述

原题目描述:

原文链接:加载失败,请重新获取