zcmimi's blog

arrow_back线段树分治共4篇文章

avatar
zc
2020-06-04 19:43:00
查看原题

点击跳转

先了解[WC2011]最大XOR和路径的做法

线段树分治+并查集+线性基

加边删边可以用按秩合并的并查集解决,遇到环就插入线性基

由于并查集无法删除元素,删边可以用线段树分治处理(转化为每条边在一个时间段存在)

avatar
zc
2020-04-23 14:02:00
查看原题

点击跳转

线段树分治+LCT

一个非常暴力的思路

FBI WARNING: 极有可能因为常数巨大而超时

把询问(修改)时间看成序列,每条边在这个序列上的一段区间出现

avatar
zc
2020-04-20 17:17:00
查看原题

点击跳转

要转化为加边,之后用并查集维护是否连通就可以了(带权维护连通块大小,为n的时候说明全部连通)

每条边都在特定的时间段中出现

由于加边完还要删掉这里使用按秩合并

avatar
zc
2020-04-19 00:28:00
查看原题

点击跳转

定义

二分图又称作二部图,是图论中的一种特殊模型。

G=(V,E)是一个无向图,

如果顶点V可分割为两个互不相交的子集(A,B),

并且图中的每条边i\leftrightarrow j所关联的两个顶点ij分别属于这两个不同的顶点集(i \in A,j \in B),

则称图G为一个二分图。

简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

判断

区别二分图,关键是看点集是否能分成两个独立的点集。

无向图G为二分图的充分必要条件是: G至少有两个顶点,且其所有回路的长度均为偶数。

证明:

必要性:

G=<V,E>为一个简单无向图,G为二分图,那么可以将V分为V_1,V_2

CG中长度为l的圈,C=(v_1,v_2,...v_{l-1},v_l,v_1)

那么v_1\in V_1,v_2\in V_2,v_3\in V_1 ,\cdots,v_l \in V_2

也就是:

v_1,v_3,v_5,\cdots v_l-1 \in V_1 \\ v_2,v_4,v_6,\cdots v_l \in V_2

所以l必定为偶数

充分性:

设无向图G中每个圈的长度都是偶数,并且假定G为连通图

定义V的两个子集V_1,V_2:

任取v\in V,

V_1=\left\{v|dist(v_i,v) \mod 2 = 0\right\}

V_2=\left\{v|dist(v_i,v) \mod 2 = 1\right\}

V_1的节点间无边连接,

假若不然,设有边v_i\leftrightarrow v_j\in Ev_i,v_j\in V_1,那么vv_i以及vv_j的长> 度都是偶数,

那么vv_iv_jv这个圈的长度为奇数,与给定条件矛盾,所以边v_i\leftrightarrow v_j不存在

同理可证V_2的节点间无边连接

回归正题,我们要判断是否是二分图,只需要判断图里是否存在奇环就可以了

解法一

link-cut tree

考虑到每条边最后都是要删掉的,那么当构成环时,我们就可以将该环中最早要被删掉的边给删去,因为这样一来不会影响连通性,二来又可以化环为链。

添加一条边的时候,若两端未连通,直接连边即可

若两端已经连通,这时一定会形成一个环,为了维护LCT,连接两端时,我们需要把环上消失时刻最早的边给删去,如果是奇环则把这条边加入集合

删边时如果是LCT上的边则断开,在集合中则将其从集合中删除

查询时若集合中没有边,则为二分图

1/1
Search
search