【题目】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; }
