HDU - 5952(暴力DFS)

news/2024/11/29 5:36:04/

范围这么小一看就是暴力。

直接爆的话会T

每个点从小到大,找出包括这个点的所有满足的团,按照这样的方向,可以保证找过的点一定不会再找。

#include <bits/stdc++.h>
using namespace std;
int m[105][105];
vector<int>es[1111];
int N, M, S;
int ans;
int E;
int s;
int v[1111];
bool check(int x) {for(int i = 1 ; i <= s ; i++) {if(!m[v[i]][x])return false;}return true;
}
void dfs(int x) {if(s == S) {ans++;return ;}for(int i = 0 ; i < es[x].size() ; i++) {if(check(es[x][i])) {v[++s] = es[x][i];dfs(es[x][i]);s--;}}
}
void Init() {ans = 0;E = 0;memset(m,0,sizeof(m));memset(v,0,sizeof(v));for(int i =  0 ; i< 1000; i++) es[i].clear();
}
int main() {int T;cin >> T;int from, to;while(T--) {Init();cin >> N >> M >> S;for(int i = 0 ; i < M ; i++) {cin >> from >> to;es[min(from,to)].push_back(max(from,to));m[from][to] = 1;m[to][from] = 1;}for(int i = 1 ; i <= N ; i++) {s = 0;v[++s] = i;dfs(i);}cout << ans << endl;}
}


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

相关文章

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…

hdu5952 Counting Cliques

一个关于图的需要dfs剪枝的暴力题&#xff0c;想了半天没什么思路&#xff0c;后来室友和我说的想法。 因为给你一个图&#xff0c;数大小为s的联通图的个数&#xff0c;连通图就是所有的点两两相连通&#xff0c;首先遍历i从1~n&#xff0c;找到和i相邻的点&#xff0c;如果 …