E - Counting Cliques HDU - 5952 DFS+剪枝

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

数据范围那么小,妥妥的暴搜,这里要注意剪枝

枚举每个点,从每个点开始搜索,找到大小为s的完全图

剪枝点:

1. 对于度数进行剪枝,如果一个点的度数小于s-1则其不可能被存在在完全图中
2. 对于枚举的点进行剪枝,已经遍历过的点就不再遍历

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool mm[105][105];
int vis[105];
int vis1[105];
vector<int> m[105];
int du[105];

int stk[105];
int top=0;

vector<int> a;
ll ans = 0;
int ct=0;

int n,m1,s;



void dfsdu(int cur)
{
    int siz = m[cur].size();
    for(int i=0;i<siz;i++)
    {
        int to = m[cur][i];
        if(du[to]>0&&vis[to]==0)
        {
            du[to]--;
            if(du[to]<s-1)
            {
                vis[to]=1;
                du[to]=0;
                dfsdu(to);
            }
        }
    }
}


void dfsfind(int x,int step,int now)
{

    if(step>=s)
    {
        ans++;
        return ;
    }

    int siz = a.size();
    for(int i=now;i<siz;i++)
    {
        int to = a[i];
        if(vis1[to]==ct) continue;
        int f=1;
        for(int j=0;j<top;j++)
        {
            f &= mm[to][ stk[j] ];
        }
        if(!f) continue;
        vis1[to]=ct;
        stk[top++] = to;
        dfsfind(to,step+1,i+1);
        top--;
        vis1[to]=0;
    }
}




int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    int T;
    int v,u;
    scanf("%d",&T);
    while(T--)
    {
        ct=1;
        ans = 0;
        memset(vis1,0,sizeof(vis1));
        memset(mm,0,sizeof(mm));
        memset(vis,0,sizeof(vis));
        memset(du,0,sizeof(du));

        scanf("%d%d%d",&n,&m1,&s);
        for(int i=0;i<=n;i++)
        {
            m[i].clear();
        }

        for(int i=0;i<m1;i++)
        {
            scanf("%d%d",&u,&v);
            u--,v--;
            mm[u][v]=1;
            mm[v][u]=1;
            du[v]++;
            du[u]++;
            m[u].push_back(v);
            m[v].push_back(u);
        }

        for(int i=0;i<n;i++)
        {
            if(du[i]<s-1)
            {
                vis[i]=1;
                du[i]=0;
                dfsdu(i);
            }
        }

        for(int i=0;i<n;i++)
        {
            if(du[i]<s-1)
            {
                continue;
            }
            if(!vis[i])
            {
                top=0;
                a.clear();
                for(int j=0;j<m[i].size();j++)
                {
                    if(!vis[ m[i][j] ] )
                    {
                        du[ m[i][j] ]--;
                        a.push_back(m[i][j]);
                    }
                }
                dfsfind(i,1,0);
                ct++;
                vis[i]=1;
            }
        }

        printf("%lld\n",ans);
    }


    return 0;
}