商务合作:179001057@qq.com

【DFS】【建图】【HDU5952】【求图中给定大小的团的个数】Counting Cliques

xiaoxiao2021-09-22  45

【题目】http://acm.hdu.edu.cn/showproblem.php?pid=5952

【题意】一个有N个点M条边的图,求其中由S个点构成的团的个数。一个团是一个完全子图。 

【思路】dfs走的时候,每当走到一个新的点,就将它放入“走过了”的集合里,每当连到新的点,就判断是否集合中的点都有直接到新点的边,是的话就放进集合中,否则走其余的点。只需要建从小点到大点的边就能保证不会重复遍历(也不会遗漏)。每当dfs搜完这个分支之后的情况,就将这个点从集合中拿出来,放上个点能走到的另一个点进来继续dfs。每当集合里点的个数等于所求的大小,ans++。

【代码】

#include<bits/stdc++.h> #define fuck(x) std::cout<<"["<<#x<<"->"<<x<<"]"<<endl; using namespace std; typedef long long ll; const int M=2e5+5; const int inf=1e9+5; int n,m,s; struct node { int v,nxt; } edge[1005]; int head[105],ei; void addedge(int u,int v) { edge[ei].v=v; edge[ei].nxt=head[u]; head[u]=ei++; } int mp[105][105]; int ans; int a[15];//放点的集合 void dfs(int x) { if(a[0]==s) { ans++; return; } for(int i=head[x]; i!=-1; i=edge[i].nxt) { int flag=0; int &v=edge[i].v; for(int j=1; j<=a[0]; j++) //必须集合中每个点都有到v的边,v才能加入 { if(mp[a[j]][v]==0) { flag=1; break; } } if(flag==0) { a[0]++; a[a[0]]=v; dfs(v); //dfs完成后把这个点从集合中取出 a[0]--; } } return; } int main() { int T; scanf("%d",&T); while(T--) { memset(head,-1,sizeof(head)); memset(mp,0,sizeof(mp)); ei=0; ans=0; scanf("%d%d%d",&n,&m,&s); for(int i=0; i<m; i++) { int a1,a2; scanf("%d%d",&a1,&a2); addedge(a1,a2); //只建从小点到大点的边 mp[a1][a2]=mp[a2][a1]=1; //存两个点之间有边 } for(int i=1; i<=n; i++) { a[0]=1;//集合元素个数 a[1]=i;//第一个元素 dfs(i); } printf("%d\n",ans); } return 0; }

 

商务合作:179001057@qq.com

CopyRight © 2010-至今 All Rights Reserved
Processed: 0.017, SQL: 9