HDU5952 Counting Cliques

题目大意

一张n个点，m条边的图，找S个点的完全图有多少个。
(n<=100,m<=1000,2<=s<=10)
题目链接

思路

从每一个点开始找，如果能找齐S个结点的完全图就ans++，按节点序号从小到大的顺序找以免重复。如果当前结点的度不够s-1，可以直接忽略。

注意，扩展下一个结点要用邻接链表，判断是否连边要用矩阵，否则会超时。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

int tu[105][105],T,n,m,s,du[103],tuu[103][103];
int cnt,t[15],ans;

void dfs(int dang)
{
    if(cnt==s)
    {
        ans++;
        return ;
    }
    for(int i=1;i<=tu[dang][0];i++)
    {
        if(du[tu[dang][i]]<s-1)continue;
        int f=1;
        for(int j=1;j<=cnt;j++)
        {
            if(!tuu[tu[dang][i]][t[j]])
            {
                f=0;
                break;
            }
        }
        if(f)
        {
            t[++cnt]=tu[dang][i];
            dfs(tu[dang][i]);
            cnt--;
        }
    }
    return ;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&s);
        memset(tu,0,sizeof(tu));
        memset(tuu,0,sizeof(tuu));
        ans=0;
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a>b)swap(a,b);
            tu[a][0]++;
            tu[a][tu[a][0]]=b;
            du[a]++,du[b]++;
            tuu[a][b]=1;
            tuu[b][a]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(du[i]<s-1)continue;
            cnt=0;
            t[++cnt]=i;
            dfs(i);
        }
        printf("%d\n",ans);
    }
}