Counting Cliques
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 539 Accepted Submission(s): 204Problem DescriptionA clique is a complete graph, in which there is an edge between every pair of the vertices. Given a graph with N vertices and M edges, your task is to count the number of cliques with a specific size S in the graph.InputThe first line is the number of test cases. For each test case, the first line contains 3 integers N,M and S (N ≤ 100,M ≤ 1000,2 ≤ S ≤ 10), each of the following M lines contains 2 integers u and v (1 ≤ u < v ≤ N), which means there is an edge between vertices u and v. It is guaranteed that the maximum degree of the vertices is no larger than 20.OutputFor each test case, output the number of cliques with size S in the graph.Sample Input3 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 6Sample Output3 7 15SourceRecommendjiangzijing2015 | We have carefully selected several similar problems for you: 5960 5959 5958 5957 5956Statistic | Submit | Discuss | Note
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5952
题目大意：
给N个点M条边，求大小位S的集合的个数，要求集合内的元素两两有边（完全图）。
题目思路：
【DFS+剪枝】
每个点最多20条出边。暴力。
首先去掉边数<S-1的点，枚举剩下的X，枚举完X可以把X的所有边删掉。加几个小剪枝即可。
1 // 2 //by coolxxx 3 //#include<bits/stdc++.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string> 7 #include<iomanip> 8 #include<map> 9 #include<stack> 10 #include<queue> 11 #include<set> 12 #include<bitset> 13 #include<memory.h> 14 #include<time.h> 15 #include<stdio.h> 16 #include<stdlib.h> 17 #include<string.h> 18 //#include<stdbool.h> 19 #include<math.h> 20 #pragma comment(linker,"/STACK:1024000000,1024000000") 21 #define min(a,b) ((a)<(b)?(a):(b)) 22 #define max(a,b) ((a)>(b)?(a):(b)) 23 #define abs(a) ((a)>0?(a):(-(a))) 24 #define lowbit(a) (a&(-a)) 25 #define sqr(a) ((a)*(a)) 26 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 27 #define mem(a,b) memset(a,b,sizeof(a)) 28 #define eps (1e-8) 29 #define J 10000 30 #define mod 2147493647 31 #define MAX 0x7f7f7f7f 32 #define PI 3.14159265358979323 33 #define N 104 34 #define M 2004 35 using namespace std; 36 typedef long long LL; 37 double anss; 38 LL aans; 39 int cas,cass; 40 int n,m,lll,ans,sz; 41 int last[N]; 42 struct xxx 43 { 44 int next,to; 45 }a[M]; 46 int b[N],c[N],in[N]; 47 void add(int x,int y) 48 { 49 a[++sz].next=last[x]; 50 a[sz].to=y; 51 last[x]=sz; 52 } 53 bool ma[N][N]; 54 void dfs(int top,int now) 55 { 56 if(top-1+lll-now<cas)return; 57 if(top==cas+1) 58 { 59 ans++; 60 return; 61 } 62 int i,j,to; 63 for(i=last[now];i;i=a[i].next) 64 { 65 to=a[i].to; 66 if(!ma[c[now]][c[to]] || to<now)continue; 67 for(j=1;j<top;j++) 68 if(!ma[c[to]][b[j]])break; 69 if(j<top)continue; 70 b[top]=to; 71 dfs(top+1,to); 72 b[top]=0; 73 } 74 } 75 int main() 76 { 77 #ifndef ONLINE_JUDGE 78 freopen("1.txt","r",stdin); 79 // freopen("2.txt","w",stdout); 80 #endif 81 int i,j,k; 82 int x,y,z; 83 // init(); 84 for(scanf("%d",&cass);cass;cass--) 85 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++) 86 // while(~scanf("%s",s)) 87 // while(~scanf("%d%d",&n,&m)) 88 { 89 mem(ma,0);mem(in,0);mem(last,0);ans=0;lll=0;sz=0; 90 scanf("%d%d%d",&n,&m,&cas); 91 for(i=1;i<=m;i++) 92 { 93 scanf("%d%d",&x,&y); 94 in[x]++,in[y]++; 95 ma[x][y]=ma[y][x]=1; 96 } 97 for(i=1;i<=n;i++) 98 if(in[i]>=cas-1) 99 c[++lll]=i; 100 for(i=1;i<=lll;i++) 101 for(j=i+1;j<=lll;j++) 102 if(ma[c[i]][c[j]]) 103 add(i,j); 104 for(i=1;i<=lll;i++) 105 { 106 b[1]=c[i]; 107 dfs(2,i); 108 for(j=last[c[i]];j;j=a[j].next) 109 ma[c[a[j].to]][c[i]]=ma[c[i]][c[a[j].to]]=0; 110 } 111 printf("%d ",ans); 112 } 113 return 0; 114 } 115 /* 116 // 117 118 // 119 */