题目大意:
对于每个s点完全子图,如果i点在子图中,那么就枚举与i有边的其他点,每加入一个点,就判断一下是否和其他已加入的点有边,如果是就可以加入,否则不能加。
思路:
对于每个s点完全子图,如果i点在子图中,那么就枚举与i有边的其他点,每加入一个点,就判断一下是否和其他已加入的点有边,
如果是就可以加入,否则不能加。
建图的时候从小的节点指向大的节点(单向边),因为最后要找的是一个无向完全图,在无向完全图中肯定可以找到一条从小节点依次
走到到大节点的有向路:比如1->2->3这样的路,边的双向信息用另一个数组存一下就行了
这样就减少了大量不必要的计算,而且不会重复,因为你在一个无向完全图里只可能找到一个,v1 < v2 < v3 ... < vx
这样的偏序关系的路,不可能再出现例如v2 < v1 < v3 < ... < vx这种路,因为这么多点大小的偏序关系是唯一的,确定了一次,以后都
不会重复了,连标记去重都不用,真巧妙!
#include<bits/stdc++.h>
using namespace std;
int t, n, m, s, st[105], tp, ans;
bool mp[105][105], vis[105];
vector<int> v[105];
bool check(int x)
{for(int i = 0; i < tp; i++)if(!mp[x][st[i]])return false;return true;
}
void dfs(int u)
{if(tp == s){ans++;return ;}for(int i = 0; i < v[u].size(); i++){int to = v[u][i];if(vis[to]) continue;if(check(to)){vis[to] = true;st[tp++] = to;dfs(to);vis[to] = false;tp--;}}
}
int main()
{scanf("%d", &t);while(t--){scanf("%d%d%d", &n, &m, &s);for(int i = 1; i <= 100; i++)v[i].clear();memset(mp, false, sizeof(mp));for(int i = 0; i < m; i++){int from, to;scanf("%d%d", &from, &to);v[min(from, to)].push_back(max(from, to));mp[from][to] = mp[to][from] = true;}ans = tp = 0;for(int i = 1; i <= n; i++){st[tp++] = i;vis[i] = true;dfs(i);tp--;vis[i] = false;}printf("%d\n", ans);}return 0;
}