HDU - 5952 Counting Cliques(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.

InputThe 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.OutputFor each test case, output the number of cliques with size S in the graph.Sample Input

Sample Output

3

7

15

思路：
如何找到一个k阶的完全图？如果一个图是完全图，那么引入一个新的点，这个点与原图中的每一点都有边相连，新图还是完全图。用了num数组来记录原图上的点。建图时，、只建了从编号小的点到编号大的点之间的边。
这是由于，每次没有必要建立反向边。反而不建反向边的话，会少了去重的过程。
代码：

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define ls (t<<1)

#define rs ((t<<1)+1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int inf = 2.1e9;

const ll Inf = ;

const int mod = ;

const double eps = 1e-;

const double pi = acos(-);

vector<int>u[maxn];

int n,m,k;

int ans;

int top;

int num[maxn];

bool mp[maxn][maxn];

void dfs(int t,int d)

{

    if(d==k){ans++;return;}

    int siz = u[t].size();

    bool flag = false;

    for(int i=;i<siz;i++){

        int cnt = u[t][i];

        flag = false;

        for(int j=;j<=top;j++){

            if(!mp[cnt][num[j]]){flag = true;break;}

        }

        if(flag){continue;}

        num[++top]=cnt;

        dfs(cnt,d+);

        top--;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        ans = ;

        scanf("%d%d%d",&n,&m,&k);

        memset(mp,,sizeof(mp));

        for(int i=;i<=n;i++){

            u[i].clear();

        }

        int x,y;

        for(int i=;i<=m;i++){

            scanf("%d%d",&x,&y);

            if(x>y){swap(x,y);}

            u[x].push_back(y);

            mp[x][y]=mp[y][x]=true;

        }

        for(int i=;i<=n;i++){

            num[++top]=i;

            dfs(i,);

            top--;

        }

        printf("%d\n",ans);

    }

    return ;

}

秒客网

HDU - 5952 Counting Cliques(DFS)

相关文章