拓扑排序用bitset处理相同排名的集合
前言
拓扑排序可以在有向无环图中以偏序求出全序,但是在一些图中,有些结点的rank是一样高的,(除非题目有特殊说明,编号小的rank高等情况),这样是不能求出正确的rank的。这时候,我们可以加入bitset,用bitset处理相同rank的结点集。
bitset
使用头文件 bitset
bitset类似于一个bool类型的数组,存放着01。可以在定义的时候进行初始化操作,可以用下标进行访问,也是从0开始,并且从默认最右边的一位为[0](结合二进制数,其实很人性化),定义、访问及初始化方法如下:
1 | int main() |
bitset的一些内置方法:
s.set():把s所有位初始化为1
s.reset():把s所有位初始化为0
s.set(k):把s的第k位设置为1
s.reset(k):把s的第k位设置为0
s.count():返回1的个数
s.any():返回是否有1
s.none():返回是否没有1
另外bitset支持位运算,这也是它很重要的一个优点。
拓扑排序使用bitset
先上一个例题:核弹剑仙
这题其实就是让你求每个结点的rank,并且可能有并列的情况,这时候我们就可以用bitset和拓扑来进行转移,bitset[i][j]表示结点j是否比i的rank高。
建图的时候u到v的单向路径表示u的rank高于v的rank,这样我们拓扑排序+bitset进行转移即可。
最后配合s.count()进行输出
AC代码:
1 | ll head[1010]; |