HDU - 5952 暴力dfs

news/2024/11/29 5:34:17/

题意:

在一个图中计算大小为s的团有多少个。

思路:

直接暴力搜索,但是要注意搜的过程很显然会出现重复,这时候我们搜索的时候其实可以选择每次新加入的点要比当前的已经完成的子图中的点要大,这样就可以避免枚举的时候出现重复,既然这样可行,我们可以换一种思路,直接在建图的时候只保存由小点指向大点的单向边即可,很巧妙。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 105;int n, m, s, ans;
vector <int> G[MAXN];
bool mp[MAXN][MAXN];
int st[MAXN];void dfs(int u, int num) {if (num == s) {++ans;return;}int cnt = G[u].size();for (int i = 0; i < cnt; i++) {int v = G[u][i];bool flag = true;for (int j = 0; j < num; j++) {if (!mp[v][st[j]]) {flag = false;break;}}if (flag) {st[num] = v;dfs(v, num + 1);}}
}int main() {int T;scanf("%d", &T);while (T--) {scanf("%d%d%d", &n, &m, &s);memset(mp, false, sizeof(mp));for (int i = 1; i <= n; i++) G[i].clear();for (int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);G[u].push_back(v);mp[u][v] = mp[v][u] = true;}ans = 0;for (int u = 1; u <= n; u++) {st[0] = u;dfs(u, 1);}printf("%d\n", ans);}return 0;
}


http://www.ppmy.cn/news/363407.html

相关文章

HDU - 5952(暴力DFS)

范围这么小一看就是暴力。 直接爆的话会T 每个点从小到大&#xff0c;找出包括这个点的所有满足的团&#xff0c;按照这样的方向&#xff0c;可以保证找过的点一定不会再找。 #include <bits/stdc.h> using namespace std; int m[105][105]; vector<int>es[1111]…

HDOJ 5952 Counting Cliques【2016沈阳现场赛】【暴力】

暴力姿势永远学不会的姿势 先说题意&#xff1a;n点m条边&#xff0c;问图中有多少种情况是&#xff1a;有s个点两两相连&#xff08;问子图的独立团&#xff0c;其中点数为s&#xff09; 看到数据量其实并不大&#xff0c;n是100&#xff0c;m是1000&#xff0c;s最大为10 还…

HDU 5952 Counting Cliques 爆搜

题目 HDU 5952 分析 题目数据很小&#xff0c;可以考虑暴力搜索。为了防止重复&#xff0c;建立一个小编号点指向大编号点的图&#xff0c;这样就不会重复了&#xff0c;因为搜索出来的序列一定是递增的。 这道题目让我懂得了&#xff0c;有时候TLE&#xff0c;不要总…

hdu 5952 - dfs+优化

题目链接:点击打开链接 题解思路:一开始直接每个枚举T了,后来直接找有连接的居然过了 。每次看这个点是否能加入这个团&#xff0c;然后分加入和不加入两种情况dfs就可以了。 代码: #include<bits/stdc.h> using namespace std; typedef long long ll; const int mx 1e…

HDU - 5952 Counting Cliques (dfs)

题目链接&#xff1a; Counting Cliques 题意&#xff1a;一个有N个点M条边的图&#xff0c;球其中由S个点构成的团的个数。一个团是一个完全子图。 题解&#xff1a;拿到这题想了好久。。没想到dfs就完事了。就dfs一下&#xff0c;回溯一下就ok了&#xff0c;铜牌题。 #includ…

Counting Cliques HDU - 5952

题目&#xff1a;https://vjudge.net/contest/194395#problem/E 题目大意 给你一个无向图&#xff0c;让你求其中大小为s的完全图分量。 分析 暴力来做&#xff0c;设置一个集合&#xff0c;dfs当前点是否与集合中的点都有边&#xff0c;边界为集合大小&#xff0c;会超时&…

HDU 5952 Counting Cliques(dfs)

http://acm.split.hdu.edu.cn/showproblem.php?pid5952 题目大意&#xff1a; n个点 m条边的无向图 问节点个数为s的完全子图个数 分析&#xff1a; 一开始以为是规律题找了半天规律 发现重复的情况没法处理 自己太菜了处理不了 后来就想暴力 直接暴…

Counting Cliques HDU - 5952 (暴力搜索)

Counting Cliques HDU - 5952 &#xff08;暴力搜索&#xff09; 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…