HDU5952-Counting Cliques(暴搜+图的完全子图)

题目链接:hdu5952-Counting Cliques

题意:
​ 给定一个无向图,然后给定一个s,求该图中有多少个节点数为s的团。
​ (认真读题,比赛时以为是数圈的个数QAQ
题解:
​ 建图:因为是无向图,答案序列1-2-3-4-5和2-3-4-5-1等价,所以由序号较小的点向序号较大的点建有向图,然后再用0-1矩阵保存原图。
​ 直接暴搜,然后注意剪枝,因为团的定义是完全子图,所有判断一个新点是否加入团中时,要看该点与团中的所有节点之间是不是都存在边。
参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,s,st,ans;
int path[15];
vector<int> edge[109];
bool mp[109][109],used[109];
void dfs(int u,int step)
{
    bool flag=0;
    for(int i=0;    i<step; i++)
    {
        if(mp[u][path[i]]==0)
        {
            flag=1;
            break;
        }
    }
    if(flag)
        return;
    else
    {
        path[step]=u;
        if(step==s-1)
        {
            ans++;
            return;
        }
    }
    for(int i=0;    i<edge[u].size(); i++)
    {
        int v=edge[u][i];
        if(used[v])
        {
            used[v]=0;
            dfs(v,step+1);
            used[v]=1;
        }
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&s);
        memset(mp,0,sizeof(mp));
        for(int i=1;    i<=n;   i++)
            edge[i].clear();
        for(int i=1;    i<=m;   i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            mp[u][v]=mp[v][u]=1;
        }
        ans=0;
        memset(used,1,sizeof(used));
        for(int i=1;    i<=n;   i++)
        {
            used[i]=0;
            dfs(i,0);
            used[i]=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。