主题

主题

 
   

4025: 二分图

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4025

Description

神犇有一个n个节点的图。因为神犇是神犇,所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了,于是他想考考你。

Input

输入数据的第一行是三个整数n,m,T。

第2行到第m+1行,每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点,这条边在start时刻出现,在第end时刻消失。

Output

输出包含T行。在第i行中,如果第i时间段内这个图是二分图,那么输出“Yes”,否则输出“No”,不含引号。

Sample Input

3 3 3

1 2 0 2

2 3 0 3

1 3 1 2

Sample Output

Yes

No

Yes

HINT

样例说明:

0时刻,出现两条边1-2和2-3。

第1时间段内,这个图是二分图,输出Yes。

1时刻,出现一条边1-3。

第2时间段内,这个图不是二分图,输出No。

2时刻,1-2和1-3两条边消失。

第3时间段内,只有一条边2-3,这个图是二分图,输出Yes。

数据范围:

  1. n<=100000,m<=200000,T<=100000,1<=u,v<=n,0<=start<=end<=T。


个人解法:

本题是codeforces某题的弱化版……或者说codeforces有一道题是本题的强化版。

很早以前就想写这道题,然而当时C++STL造诣不深(现在也是),分治造诣不深(现在也是),并查集造诣不深(现在也是),从而被本蒟列入不可做名单。

我们按照时间分治。

如果一条边出现的时间恰好是当前分治结构的时间(也就是这一段时间,这条边都会覆盖),我们就操作这条边。

剩余的边我们根据其出现的时间划分到左边集合与右边集合。如果跨mid的,我们按照类似线段树的方法,分裂开来。

如果连接的时候,发现出现了奇环,那么当前这一段时间都不可能是二分图了。记录一下即可。分治到最底层仍然没有出现奇环,就说明当前这个时刻是二分图。

判断奇环我们可以使用一个带权并查集。

用一个带权并查集。权表示到fa的距离。

那么连接一条边:原图就是(u,v)=1,对应到并查集上面就是Fa[fv]=fu,Dis[fv]=Dis[u]+Dis[v]+1。

由于只需要搞奇偶性,所以我们令奇数为1偶数为0,原图就是(u,v)=1,对应到并查集上面就是Fa[fv]=fu,Dis[fv]=Dis[u]^Dis[v]^1。

在回溯的上取消操作即可。之所以用并查集正好是因为可以方便取消之前的操作。虽然LCT可以做到同样的效果,但是LCT常数巨大。而且如果用LCT就有另外一种算法,而不必分治,还可以减少一个log(但是不保证实际运行更快)。

由于我们需要分裂集合,于是我们需要带一个vector的参数下来表示这个集合。

空间复杂度是O(nlogn)的,每一层都需要一个O(n)的vector在不同的递归结构里面表示集合。

(我们假设n=m=T,方便分析)

时间复杂度是O(nlog^2n)的。但是并不是说简单的分治+并查集就是log^2n。

  1. 按照时间分治带一个logn。

  2. 并查集按秩合并(我们需要取消操作,所以不能路径压缩,当然高深一点的理论,按照Po姐的说法,路径压缩这种均摊复杂度的东西在分治结构里面是没有用的)带一个logn。

  3. 考虑分裂的边所增加的复杂度的话,我们只需要发现,一条边最多只会被分裂logn次。

那么这么计算会变为O(nlog^3n)的。

但是事实上我们发现,在一个递归结构里面,一条边如果被操作(加入并查集)了,就不会再分裂。如果分裂了,就不会再操作。那么我们考虑一条边的历程,最多会被分裂为O(logn)条边(根据线段树的复杂度证明),每一条边都会有O(logn)的操作(并查集复杂度),所以一条边的时间复杂度为O(log^2n)。总的复杂度就是O(nlog^2n),这样分析,与分治无关(分治体现在类似线段树的那一段分析中)。


代码如下:

https://code.csdn.net/snippets/2280351


久违的1A。

 
 
评论