对并查集的深入理解

对并查集的理解：

1、树的深度最多是2
2、一般set结构体都需要有一个rank[]来记录有多少孩子，孩子多的，以后还是父亲
3、并查集：不相交集合，这个概念一定得搞清楚！



欢迎拍砖！


评论

发表评论

此博客中的热门博文

提交了30次才AC －－－【附】POJ 2488解题报告

NND,这道题目，竟然提交了30次，搞的我晕过去了都！花费了将近12个小时！！ 感一下，叹一声！如今的ACM，不仅锻炼编程，还锻炼了心理承受能力！！ 1、注意格式，后面有一个空行 2、注意输出的时候的字典序－－什么叫字典序，要弄清楚 3、注意国际象棋的棋盘－－ 横的是字母，竖的是数字－－ 一定要按照这个格式，否则即使是答案对，也WA 有26次，全部栽在第3点上 3次栽在第二点上 1次栽在第一点上 PS:因为是字典序，所以，可以肯定只需要从（1，1）开始即可。不需要注意那句话：start at any position of the chessboard. Source Code Problem: 2488 User: omycle Memory: 192K Time: 360MS Language: C++ Result: Accepted Source Code #include <iostream> #include <string> using namespace std ; bool ok = false ; int col = 0 ; int row = 0 ; int zoufa [ 8 ][ 2 ]= {{ - 2 ,- 1 } , { - 2 , 1 } , { - 1 ,- 2 } , { - 1 , 2 } , { 1 ,- 2 } , { 1 , 2 } , { 2 ,- 1 } , { 2 , 1 }} ; // int flag [ 50 ][ 50 ]; //第0行的，第零列的全不要 typedef struct { int x ; int y ; } Step ; Step step [ 100 ]; //记录路径呀 Step step_c [ 100 ]; int Count = 0 ; void print ( int n ); //数组比较函数 bool cmpint () { int i = 0 ; while ( i < col * row ) { if ( step_c [ i ]. x < step [ i ]. x ) return false ; //不用 if ( step_c [ i ]. y < step [ i ]...
阅读全文

笔记

TUN/TAP:是操作系统内核中的虚拟网络设备。不同于普通靠硬件网路板卡实现的设备，这些虚拟的网络设备全部用软件实现，并向运行与操作系统上的软件提供与硬件的网络设备完全相同的功能。 TUN:等同于一个以太网设备，它操作第二层数据包如以太网数据帧 TAP:模拟了网络层设备，操作第三层数据包比如IP数据封包 操作系统 通过TUN/TAP设备向 绑定该设备的用户空间的程序 发送数据，反之， 用户空间的程序 也可以像操作硬件网络设备那样，通过TNU/TAP设备发送数据。在后种情况下，TUN/TAP设备向 操作系统的网络栈 投递（或“注入”）数据包，从而模拟从外部接受数据的过程。   ------ 基于优先级抢占式调度 ：系统中每个任务都有一个优先级，内核总是将CPU分配给处于就绪态的优先级最高的任务运行。如果系统发现就绪队列中有比当前运行任务更高的优先级任务，就把当前运行任务置于就绪队列中，调入高优先级任务运行。系统采用优先级抢占方式进行调度，可以保证重要的突发事件及时得到处理。
阅读全文

汇编代码杂记

一直没有在汇编中写过代码。而且读一些复杂的代码，还有一些吃力。并且自己在ARM体系结构方面的基本功非常薄弱，仅仅是看过杜春雷同学写的那本《ARM体系结构与编程》的教材，偶尔看一下网上同学总结的一些ARM指令的野史笔记。 由于要追踪一下项目中页表的建立流程，由于枝叶比较繁茂，并且深入汇编代码之中，因此，不能充分利用野蛮并且笨拙的Printk，于是便需要在汇编中调用自己写的C函数，然后让流程重新回到汇编中，继续徜徉。 让汇编调用C中的函数，在网上的文章一抓一大把，可是让C中的函数重新返回到汇编中，不着痕迹得继续运行，却没有这样的总结性文章。无奈之下，重新从download.csdn.net中下载到ARM指令集（以前看过，但由于一次误操作，将之永久驱逐出俺的硬盘中），By the way，这个ARM指令集确实不错，有需要的同学到csdn资源中心去自己寻找吧。下面把俺的情况说一下： ENTRY(cpu_arm926_set_pte_ext) mov r3, r1 eor     r3, r3, #L_PTE_PRESENT | L_PTE_YOUNG | L_PTE_WRITE | L_PTE_DIRTY bic     r2, r3, #PTE_SMALL_AP_MASK bic     r2, r2, #PTE_TYPE_MASK orr     r2, r2, #PTE_TYPE_SMALL tst     r3, #L_PTE_USER                 @ User? orrne   r2, r2, #PTE_SMALL_AP_URO_SRW tst     r3, #L_PTE_WRITE | L_PTE_DIRTY  @ Write and Dirty? orreq   r2, r2, #PTE_SMALL_AP_UNO_SRW tst     r3, #L_PTE_PRESENT | L_PTE_YOUNG        @ Present and Young? movne   r2, #0 b  hypervisor_set_pte 我要做的事情是，在hypervisor_set_pte之前调用一个自写的C函数。由于后面还有b hypervisor_set_pte.而hypervisor_set_pte这个函数返回后，返回到lr所指定的地址中...
阅读全文