DFS
字符串、线性表、队列、栈、哈希表、dfs、bfs
题目列表： 1. 字符串 无重复字符的最长子串 （中等难度） 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 AC代码，展开查看 class Solution { public: int lengthOfLongestSubstring(string s) { int res ......
第 369 场周赛(简单位运算，分类讨论，dfs，树形dp)
简单位运算模拟 class Solution { public: int findKOr(vector<int>& nums, int k) { vector<int> bit(32, 0); for(int i = 0; i < 31; i ++ ) { int cnt = 0; for(auto ......
数据结构与算法 | 深搜（DFS）与广搜（BFS）
在查找二叉树某个节点时，如果把二叉树所有节点理理解为解空间，待找到那个节点理解为满足特定条件的解，对此解答可以抽象描述为： _在解空间中搜索满足特定条件的解_，这其实就是搜索算法（Search）的一种描述。当然也有其他描述，比如是“指一类用于在数据集合中查找特定项或解决问题的算法”，又或者是“指通过... ......
P9669 [ICPC2022 Jinan R] DFS Order 2
Description P 有一棵树，根节点是 \(1\)，总共有 \(n\) 个节点，从 \(1\) 到 \(n\) 编号。 他想从根节点开始进行深度优先搜索。他想知道对于每个节点 \(v\)，在深度优先搜索中，它出现在第 \(j\) 个位置的方式有多少种。深度优先搜索的顺序是在搜索过程中访问节点 ......
Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees（ DFS ）
Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees 思路： 在输入树的边的同时记录他们的输入顺序 从 1 开始跑 DFS ，遇到未连上的边时 ， 有两种情况（用 q 表示当前点的顺序序号） 1.边的顺序在这个点连上之前，那么 DFS 的 ......
DFS 剪枝
DFS 剪枝 \(DFS\) 是一种常见的算法，大部分情况下，很少会爆搜为正解的题目。因为 \(DFS\) 的时间复杂度特别高。 我们可以先写一段 dfs 的伪代码 int ans = 最坏情况, now; // now 为当前答案 void dfs(传入数值) { if (到达目的地) { ans ......
【DFS】129. 求根节点到叶子结点的和
链接 https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/ 思路 时刻记住，DFS是递归的一种。而解决递归，最朴素的思路就是：递归的定义就是递归的解。 题目要求我们求根节点到叶子结点的和，我们要提供一个值保持其状态，退出 ......
【经典题目】【循环DFS】生成数组的全排列
问题描述 给你一个数组，生成这个数组中元素的全排列。 思路 经典的循环dfs。要点是我们需要设置visited数组来指代其是否被遍历过。 代码 class Solution: def islandPerimeter(self, grid): if not grid: return [] visite ......
DFS
题目：https://www.luogu.com.cn/problem/P1216 //还需理解 #include <iostream> #include <algorithm> #include <cstring> using namespace std; int r; int num[1005] ......
P9233 [蓝桥杯 2023 省 A] 颜色平衡树 （dfs序 莫队）
P9233 [蓝桥杯 2023 省 A] 颜色平衡树 （dfs序 莫队） 莫队原理:https://zhuanlan.zhihu.com/p/115243708 对于树上的每个结点，按照 dfs 序打上时间戳，这样就可以把每一个结点对应的子树的答案转化为一个区间的答案。将子树询问离线下来变成 \(n ......
【LeetCode递归】括号生成，使用dfs
括号匹配 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例 1： 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"] 示例 2： 输入：n = 1 输出：["()"] 提示： 1 < ......
JAVA图搜索算法之DFS-BFS
图算法DFS与BFS BFS和DFS代表对图进行遍历，即搜索的算法，搜索算法中常用的只要有两种算法:深度优先遍历(Depth-First-Search : DFS)和广度优先遍历(Breadth-First-Search : BFS)。一个图结构可以用来表示大量现实生活中的问题，比如，道路网络，计算 ......
DFS 与 BFS
简介 状态：解决问题所关注的属性的集合。 转移：状态之间的变化过程。 搜索：处理状态转移、寻找新状态、枚举（遍历）所有状态的一种算法思想。 搜索树：状态和有效转移形成的树形结构，每个状态只会被扩展一次。 深度优先搜索 全称为 Depth-First Search，简称 DFS、深搜。 这个算法一般采 ......
dfs 与 bfs
$$dfs$$ 深度优先搜索，全称 Depth First Search，通常有两种意义：递归暴力枚举每种情况、图论中用于遍历或搜索图的算法。 搜索：递归暴力枚举每种情况 OI-wiki Link 没有什么好说的，经常用于打暴力，像 xhr 神仙就可以用它打出 HN 2023 小学组 S 1=。 洛 ......
[DFS]电话号码的字母组合
电话号码的字母组合 这道题目的本质是笛卡尔积问题，可以通过DFS求解，分别采用C/Java语言实现 #include <stdio.h> #include <stdlib.h> char *phoneMap[10] = {"", "", "abc", "def", "ghi", "jkl", "mn ......
续 dfs 八皇后问题（9/24）
第一种 类似于上一个题目得变形 #include<iostream> using namespace std; const int N = 20; int n; char p[N][N]; bool col[N], dg[N*2], udg[N*2];//注意范围的设置 void dfs(int u ......
dfs(排列数字 n皇后问题) （9/21）
dfs排列数字 #include<iostream> using namespace std; const int N=10; int path[N]; bool str[N]; int n; void dfs(int u){ if(u==n){ for(int i=0;i<n;i++)printf ......
dfs 序 O(nlogn)-O(1) 求 LCA
学点分树，发现不会询问复杂度 \(O(1)\) 的 LCA。于是被迫递归式学习。 我们设 \(dfn_i\) 表示点 \(i\) 在 dfs 过程中第几个被访问到，把点按访问到的顺序排序得到的序列叫 dfs 序。 考虑 \(u\) 和 \(v\) 在 dfs 序上的位置之间的这一段序列有什么。 设 ......
AtCoder Beginner Contest 126 D (图论、LCA性质、DFS、思维、*1200)
D - Even Relation 给你一棵树 (结点个数为 $ n(n \le 10^5) $, 现在需要将树上所有结点染成白色或黑色, 打印一种可行的方案(将 $ i $ 号点染成白色则输出 0, 否则, 输出 1), 满足：同一种颜色的点之间的距离是偶数。 思路： ......
多叉树应用 包括构建 dfs遍历
力扣17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例 1： 输入：digits = "23" 输出：["ad","ae","af","bd","be ......
有关dfs序求lca的相关问题及常见问题
本文主要是用于警示自己避免犯错。 参考代码 dfs 序求 lca 的参考代码如下。 #include<bits/stdc++.h> using namespace std; const int MAXN=5e5+10,MAXLOG2N=20; int N,M,S,cnt,head[MAXN],dfn ......
DFS
DFS 261. 树状结构查询 import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static Map<String, Set<String> ......
【dfs基础题】洛谷P1219题解
题目大意 给定棋盘的规格为 \(n×n\)，现在要摆 \(n\) 个皇后，使得每个皇后不能互相攻击。 题目解答 由题意可知，如果两个皇后在同一行或同一列或同一对角线，那么就会互相攻击。 那么就简单了，若当前要摆的是第 \(i\) 个皇后，那么只需要 for 循环一遍前面的 \(i-1\) 个皇后，判 ......
【LuoGu】3047 Nearby Cows G ——两次DFS+树上DP
[USACO12FEB] Nearby Cows G 题目描述 给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 输入格式 第一行两个正整数 \(n,k\)。 接下来 \(n-1\) 行，每行两个正整数 \(u,v\)，表示 \(u ......
P2633 Count on a tree 题解（外加DFS序求LCA）
`2023-07-22 09:53:59 顶置3` # P2633 Count on a tree ## 前置小知识 # 冷门小科技:DFS-RMQ 求LCA 最近跟着洛谷榜一的博客学了一个冷门科技：DFS序求LCA，这道题刚好要求LCA，所以就刚好适用一下。 [$\color{Red}{原博客地址 ......
Acwing -- 5165. CCC单词搜索（dfs， 方向与位运算）
本题为八方向枚举，且结合枚举状态时的直角拐弯。 如图，假设我们正在枚举1号方向，它可以向7和3方向转弯，观察其二进制规律，第一位取反，及d ^ 2, 第2位为0和1， 枚举详见代。 #include<iostream> #include<cstdio> #include<cstring> #incl ......
邻接矩阵的DFS
采用递归的方法 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MaxSize 20 5 6 typedef struct{ 7 int Ver[MaxSize]; 8 int Edge[MaxSize][MaxSize]; 9 int ......
c++算法之迷宫问题 和 DFS
啥是迷宫问题？ 迷宫问题，简单来说就是在给定区域内，找到一条甚至所有从某个位置到另一个位置的移动路线。 如果细来讲，我们可以把迷宫化为一个平面矩阵，通过行、列来确定位置，对应位置不同的内容表示不同的地图信息。 在c++里，我们一般用二维数组来存储，例如n*n大小的地图就是m[n][n]，地图中存在空 ......
dfs理解——以出栈方式的字典序为例(对上一个出栈字典序的完善和强化）
笔者认为，dfs的本质在于试验每一方向和还原。 试验每一方向的含义是：将实际题目中的条件几何化为多个方向，给这些方向赋予优先级（一般采用在dfs函数中写入顺序为优先级，这样比较简单方便），按照优先级的顺序来进行试验，每个节点都有基本相同的方向和优先级的，就可以使用dfs的方式解决。 还原：还原要结合 ......
DFS和BFS及模板
## DFS和BFS及模板 ### 1. 定义 ``` DFS俗称深度优先搜索，BFS俗称宽度优先搜索。这两种算法都可以保证遍历图中所有的节点。是一种非常常见的搜索算法。 ``` ### 2. DFS思想 ![img](https://img2023.cnblogs.com/blog/2206600 ......