HDU 5952 Counting Cliques（DFS+剪枝）

Counting Cliques

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

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

题目链接：HDU 5952
很神奇的题目，当比赛做的时候一直T，没写出来，赛后看了题解发现其实只要用一个栈记录一下当前加入团的点就可以了，这样就不用遍历所有的点了，然后另外一个优化是对于大小为$S$的团，里面的任意点的度至少为$S-1$（画几个小的样例就可以发现了），因此在删点的时候把其他点的入度也更新一下，然后$DFS$的时候也不走这些入度不符合要求得点即可。然后如何排除重复计数的情况呢？比如得到${2,3,4}$之后又在$2$的另一颗搜索树中得到${2,4,3}$，对于这种情况只要保证边都是从小的编号连向大的编号即可。
代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
const int M = 1010;
struct edge
{
    int to, nxt;
    edge() {}
    edge(int _to, int _nxt): to(_to), nxt(_nxt) {}
} E[M << 1];
int head[N], tot;
int deg[N];
int n, m, s, ans;
int G[N][N];
int st[N], top;

void init()
{
    top = 0;
    ans = 0;
    CLR(head, -1);
    tot = 0;
    CLR(deg, 0);
    CLR(G, 0);
}
inline void add(int s, int t)
{
    E[tot] = edge(t, head[s]);
    head[s] = tot++;
}
void dfs(int u)
{
    st[top++] = u;
    if (top == s)
    {
        ++ans;
        st[--top] = 0;
        return ;
    }
    for (int i = head[u]; ~i; i = E[i].nxt)
    {
        int v = E[i].to;
        if (deg[v] < s - 1)
            continue;
        int flag = 1;
        for (int j = 0; j < top; ++j)
        {
            if (!G[v][st[j]])
            {
                flag = 0;
                break;
            }
        }
        if (flag)
            dfs(v);
    }
    st[--top] = 0;
}
int main(void)
{
    int TC, i, a, b;
    scanf("%d", &TC);
    while (TC--)
    {
        init();
        scanf("%d%d%d", &n, &m, &s);
        for (i = 0; i < m; ++i)
        {
            scanf("%d%d", &a, &b);
            if (a > b)
                swap(a, b);
            add(a, b);
            ++deg[a];
            ++deg[b];
            G[a][b] = G[b][a] = 1;
        }
        for (i = 1; i <= n; ++i)
        {
            if (deg[i] < s - 1)//直接删除
            {
                for (int j = head[i]; ~j; j = E[j].nxt)
                {
                    --deg[i];
                    --deg[E[j].to];
                    G[i][E[j].to] = G[E[j].to][i] = 0;
                }
            }
            else
            {
                dfs(i);
                for (int j = head[i]; ~j; j = E[j].nxt)
                {
                    --deg[i];
                    --deg[E[j].to];
                    G[i][E[j].to] = G[E[j].to][i] = 0;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}