Counting Cliques

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 184    Accepted Submission(s): 56

Problem Description

A 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. 

 

 

Input

The 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.

 

 

Output

For each test case, output the number of cliques with size S in the graph.

 

 

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

 

思路：构造一个团，如果一个点与这个团的所有点都有边，则将其加入团中，统计含s个点的团的个数。关于优化，可以建单向边来减少搜索量。

 

代码：

1 #include
     
       2 //#include
      
        3 #define db double 4 #include
       
         5 #define ll long long 6 #define vec vector
        
          7 #define Mt  vector
         
           8 #define ci(x) scanf("%d",&x) 9 #define cd(x) scanf("%lf",&x)10 #define cl(x) scanf("%lld",&x)11 #define pi(x) printf("%d\n",x)12 #define pd(x) printf("%f\n",x)13 #define pl(x) printf("%lld\n",x)14 #define MP make_pair15 #define PB push_back16 #define inf 0x3f3f3f3f3f3f3f3f17 #define fr(i,a,b) for(int i=a;i<=b;i++)18 const int N=1e3+5;19 const int mod=1e9+7;20 const int MOD=mod-1;21 const db  eps=1e-18;22 using namespace std;23 bool d[105][105];24 int n,m,s,t;25 int ans;26 vector
          
            g[N];27 void dfs(int u,int *a,int cnt)28 {29 if(cnt==s){30 ans++;31 return;32 }33 bool ok;34 for(int i=0;i
           
            v) swap(u,v);63 g[u].push_back(v);64 d[u][v]=d[v][u]=1;65 }66 for(int i=1;i<=n;i++){67 if(g[i].size()>=s-1){68 int a[105];69 a[1]=i;//构建团70 int cnt=1;71 dfs(i,a,cnt);72 }73 }74 pi(ans);75 }76 return 0;77 }