首页 > 其他分享 >dfn序,dfs序与欧拉序的区别

dfn序,dfs序与欧拉序的区别

时间:2023-04-13 10:48:06浏览次数:31  
标签:序是 子树 dfs dfn 节点 欧拉

dfn序,dfs序与欧拉序的区别

dfs序是dfs过程中对于某节点进入这个节点的子树和离开子树的顺序

满足每个节点都会在dfs序上出现恰好两次

任意子树的dfs序都是连续的

欧拉序是dfs过程中经过节点的顺序

每个节点至少出现一次(事实上出现这个节点的度次,根节点额外一次)

有时候用来配合稀疏表求最近公共祖先

dfn序是点按照dfs进入节点的顺序排列的序列

一般dfn序可以认为是dfs序的一半、是dfs序的子序列

标签:序是,子树,dfs,dfn,节点,欧拉
From: https://www.cnblogs.com/Ayaka-T/p/17312591.html

相关文章

  • 解密!FastDFS的安装及部署(实战篇)
    前言天猫、淘宝等购物网站,海量的商品图片和视频,是如何存储的?当用户访问量大时,又如何保证下载速度?分布式文件系统就是用来解决这些问题的。那么分布式文件系统该如何使用呢?别急,今天袁老师就会带领大家来学习这些非常实用的技能:分布式文件系统概述主流的分布式文件系统的介绍重点介绍......
  • 线性筛,整除分块,欧拉函数与莫比乌斯反演
    埃氏筛法说到筛质数,就不得不提到大名鼎鼎的埃氏筛法了思想非常简单,就是对于每一个素数pri[i],我们都把它的倍数筛去,譬如对于素数2来说,我们就把\(2*2,2*3,2*4,2*5....2*n\)的数全部筛掉代码voidzhishu(intn){ for(inti=2;i<=n;i++){ if(p[i]==0) for(intj=i*2;......
  • 【VINKA原厂技术支持】电源供电系列高稳定性抗干扰VK36Q4 DFN10 封装更小厚度超薄的四
    1.概述VK36Q4具有4个触摸按键,可用来检测外部触摸按键上人手的触摸动作。该芯片具有较高的集成度,仅需极少的外部组件便可实现触摸按键的检测。提供了4路直接输出功能。芯片内部采用特殊的集成电路,具有高电源电压抑制比,可减少按键检测错误的发生,此特性保证在不利环境条件的应用......
  • UVa 524 Prime Ring Problem (数论&DFS)
    524-PrimeRingProblemTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=465Aringiscomposedofn(evennumber)circlesasshownindiagram.Putnaturalnumbers  intoea......
  • UVa 10004 Bicoloring (DFS&二分图)
    10004-BicoloringTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=945In1976the``FourColorMapTheorem"wasprovenwiththeassistanceofacomput......
  • dfs入门习题
    主要记录一下个人遇见过的一些dfs的一些入门题目。有需要的可以跟着题单往下做。题单根据自己的刷题不定时更新。 第一题:https://codeforces.com/problemset/problem/510/B一道比较经典的dfs模板题。需要注意一下记忆化搜索。 **点击查看代码......
  • Leetcode(剑指offer专项训练)——DFS/BFS专项(2)
    课程顺序题目现在总共有numCourses 门课需要选,记为 0 到 numCourses-1。给定一个数组 prerequisites,它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i]=[ai,bi] 表示想要学习课程ai ,需要先完成课程bi 。请根据给出的......
  • HJ67_24点游戏算法_多维递归_DFS(深度优先搜索)
    思路:多维递归,深度有限遍历加减乘除四种情况。知识点:1、多维递归不能对传递的变量进行修改,否则无法回溯。应该传递一个新地址的变量,如代码所示,传递切片的列表,不修改列表  2、搜索遗漏。两括号比如((9-4)-1)*6选取任意一个数作为第一个运算数与24运算,不能找出所有24点的计算......
  • Leetcode(剑指offer专项训练)——DFS/BFS专项(1)
    计算除法题目给定一个变量对数组equations和一个实数值数组values作为已知条件,其中equations[i]=[Ai,Bi]和values[i]共同表示等式Ai/Bi=values[i]。每个Ai或Bi是一个表示单个变量的字符串。另有一些以数组queries表示的问题,其中queries[j]=[Cj,Dj]......
  • 欧拉函数
    欧拉函数\(\phi\)定义\(\phi(n)\)表示\(1\simn\)中与\(n\)互质的数的个数。公式先将\(n\)分解质因数,即:\(n=p_1^{\alpha_1}\cdotp_2^{\alpha_2}\\dotsp_k^{\alpha_k}\)则\(\phi(n)=n\cdot\prod_{i=1}^k(1-\dfrac{1}{p_i})\)。即\(\phi(n)=n\......