HDU 5952 Counting Cliques（dfs）

待我称王封你为后i 2022-01-09 10:05 96阅读 0赞

# 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亚洲区沈阳站-重现赛（感谢东北大学）][2016ACM_ICPC_-]

Recommend

jiangzijing2015

# 题意： #

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

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

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <string>
     5 #include <algorithm>
     6 #include <cmath>
     7 #include <vector>
     8 #include <queue>
     9 #include <map>
    10 #include <stack>
    11 #include <set>
    12 using namespace std;
    13 typedef long long LL;
    14 #define ms(a, b) memset(a, b, sizeof(a))
    15 #define pb push_back
    16 #define mp make_pair
    17 const LL INF = 0x7fffffff;
    18 const int inf = 0x3f3f3f3f;
    19 const int mod = 1e9+7;
    20 const int maxn = 100+10;
    21 bool edge[maxn][maxn];
    22 vector <int> E[maxn];
    23 int num[maxn];
    24 int p[20];
    25 int ans, n, m, s, u, v;
    26 void init() {
    27     ms(edge, 0);
    28     ms(num, 0);
    29     for(int i = 0;i<maxn;i++)   E[i].clear();
    30     ans = 0;
    31 }
    32 void dfs(int x, int len){
    33     int flag = 1;
    34     for(int i=0;i<len;i++){
    35         if(!edge[x][p[i]]){
    36             flag = 0;
    37             break;
    38         }
    39     }
    40     if(!flag){
    41         return;
    42     }
    43     p[len] = x;
    44     if(len+1==s){
    45         ans++;
    46         return;
    47     }
    48     for(int i = 0;i<E[x].size();i++){
    49         dfs(E[x][i], len+1);
    50     }
    51 }
    52 void solve() {
    53     scanf("%d%d%d", &n, &m, &s);
    54     for(int i = 0;i<m;i++){
    55         scanf("%d%d", &u, &v);
    56         E[min(u, v)].pb(max(u, v));//小的点指向大的点
    57         edge[u][v] = edge[v][u] = 1;
    58         num[u]++;
    59         num[v]++;
    60     }
    61     for(int i = 1;i<=n;i++){
    62         if(num[i]<s-1)  continue;
    63         dfs(i, 0);
    64     }
    65     printf("%d\n", ans);
    66 }
    67 int main() {
    68 #ifdef LOCAL
    69     freopen("input.txt", "r", stdin);
    70 //        freopen("output.txt", "w", stdout);
    71 #endif
    72     int T;
    73     scanf("%d", &T);
    74     while(T--){
    75         init();
    76         solve();
    77     }
    78     return 0;
    79 }

转载于:https://www.cnblogs.com/denghaiquan/p/7218233.html

[2016ACM_ICPC_-]: http://acm.hdu.edu.cn/search.php?field=problem&key=2016ACM%2FICPC%D1%C7%D6%DE%C7%F8%C9%F2%D1%F4%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B6%AB%B1%B1%B4%F3%D1%A7%A3%A9&source=1&searchmode=source
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/483a8f4de0e342e189205559af61c37f.png