Counting Cliques

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1855 Accepted Submission(s): 735

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

Sample Output

3
7
15

Source

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

Recommend

jiangzijing2015

题意：

　　给你n个点，m条边，要你在这些点里面找大小为s 的完全图（完全图是指这个图里任意两点都有一条边）。

　　因为 N 只有100个。S最大也才10。所以我们可以爆搜来解决。然后我就T了 :(

　　因为 1 2 3 如果是完全图的话，那么 2 1 3 也是。所以我们多搜了很多次。

　　如果我们建边的时候是按照小的指向大的点来建，就可以避免了很多情况。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <queue>

 #include <map>

 #include <stack>

 #include <set>

 using namespace std;

 typedef long long LL;

 #define ms(a, b) memset(a, b, sizeof(a))

 #define pb push_back

 #define mp make_pair

 const LL INF = 0x7fffffff;

 const int inf = 0x3f3f3f3f;

 const int mod = 1e9+;

 const int maxn = +;

 bool edge[maxn][maxn];

 vector <int> E[maxn];

 int num[maxn];

 int p[];

 int ans, n, m, s, u, v;

 void init() {

     ms(edge, );

     ms(num, );

     for(int i = ;i<maxn;i++)   E[i].clear();

     ans = ;

 }

 void dfs(int x, int len){

     int flag = ;

     for(int i=;i<len;i++){

         if(!edge[x][p[i]]){

             flag = ;

             break;

         }

     }

     if(!flag){

         return;

     }

     p[len] = x;

     if(len+==s){

         ans++;

         return;

     }

     for(int i = ;i<E[x].size();i++){

         dfs(E[x][i], len+);

     }

 }

 void solve() {

     scanf("%d%d%d", &n, &m, &s);

     for(int i = ;i<m;i++){

         scanf("%d%d", &u, &v);

         E[min(u, v)].pb(max(u, v));//小的点指向大的点

         edge[u][v] = edge[v][u] = ;

         num[u]++;

         num[v]++;

     }

     for(int i = ;i<=n;i++){

         if(num[i]<s-)  continue;

         dfs(i, );

     }

     printf("%d\n", ans);

 }

 int main() {

 #ifdef LOCAL

     freopen("input.txt", "r", stdin);

 //        freopen("output.txt", "w", stdout);

 #endif

     int T;

     scanf("%d", &T);

     while(T--){

         init();

         solve();

     }

     return ;

 }

巴特西

HDU 5952 Counting Cliques（dfs）

Counting Cliques

题意：

最新文章

热门文章