一个关于图的需要dfs+剪枝的暴力题，想了半天没什么思路，后来室友和我说的想法。

因为给你一个图，数大小为s的联通图的个数，连通图就是所有的点两两相连通，首先遍历i从1~n，找到和i相邻的点，如果 i 的度数大于s-1，那么把所有和 i 相邻并且度数大于s-1的点加入到一个队列（数组）中，对这个队列进行dfs找联通图的个数就行了。

一个是要想到怎么遍历的，另外一个就是dfs函数怎么写。

#include<bits/stdc++.h>
using namespace std;int gra[105][105],cnt[105],num[105],a[105]; //建立一个num来存点i的符合条件的相邻点，cnt来存每个点的度数
int n,m,s;int check(int t,int x) { //检查加入的点是不是都联通for(int i = 1;i < t;i++)if(gra[a[i]][x] == 0)return 0;return 1;
}long long dfs(int dd,int cc,int count) { //检查相邻点中有几个联通图，dd为下标，cc为num数组的长度，count为加入点的个数if(count == 0) return 1;long long ret = 0;for(int i = dd;i <= cc-count+1;i++) {a[s-count+1] = num[i];if(check(s-count+1,num[i]))ret += dfs(i,cc,count-1);}return ret;
}int main() {int t;scanf("%d",&t);while(t--) {scanf("%d%d%d",&n,&m,&s);memset(gra,0,sizeof(gra));memset(cnt,0,sizeof(cnt));for(int i = 1;i <= m;i++) {int x,y;scanf("%d%d",&x,&y);gra[x][y] = 1;gra[y][x] = 1;}for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)cnt[i] += gra[i][j]; //计算该点的度数long long ans = 0;int cc;for(int i = 1;i <= n;i++) {if(cnt[i] >= s-1) {num[1] = i;cc = 1;for(int j = i+1;j <= n;j++) {  //加入符合条件的与i相邻的点if(gra[i][j] && cnt[j] >= s-1)num[++cc] = j;}}if(cc < s) continue;/*for(int i = 1;i <= cc;i++)printf("%d ",num[i]);printf("end\n");*/a[1] = num[1];ans += dfs(2,cc,s-1);}printf("%I64d\n",ans);}
}

还是写出来了，dfs不够熟练，继续刷数位dp！嗯