bzoj 4025 二分图

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

B.二分图

题面

神犇有一个$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

$1\le n\le 100000，1\le m\le 200000，1\le T\le 100000，1\le u,v\le n，0\le start\le end\le T。$

Sample Explain

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

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

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

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

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

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

如题：二分图的话，就等价于不存在奇环，我们直接线段树分治，用并查集维护每个点与根节点间的距离即可。

我们建立一棵线段树，用时间轴来当做线段树的左右端点，每一条边出现消失的时间区间就对应着线段树上的一对$[l,r]$，将每一条边插到对应的时间区间中，最后统计答案时，只要用线段树分治，从$[1,r_{max}]$各个点都依次访问,存储答案，最后输出。

当然了，由于我们要支持撤销操作，所以不能将并查集路径压缩，这样就没有办法撤销了。

具体操作见代码吧。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
const int N=100010;
struct edge
{
	int u,v;
};
vector<edge> t[N<<2];
bool Answer[N];
int fa[N],sz[N],dist[N],n,m;
int q;
int getfa(int x)
{
	while(x!=fa[x]) x=fa[x];
	return x;
}
int dis(int x)
{
	int d=0;
	while(x!=fa[x]) d^=dist[x],x=fa[x];
	return d;
}
void change(int root,int l,int r,int ll,int rr,edge e)
{
	if(ll<=l&&r<=rr) {t[root].push_back(e);return;} 
	int mid=l+r>>1;
	if(ll<=mid) change(root<<1,l,mid,ll,rr,e);
	if(rr>mid) change(root<<1|1,mid+1,r,ll,rr,e);
}
void divide_(int root,int l,int r)
{
	vector<edge> p; p.clear();
	int mid=l+r>>1;
	bool have_ans=0;
	for(int i=0,len=t[root].size();i<len;++i)
	{
		int u=t[root][i].u,v=t[root][i].v;
		int a=getfa(u),b=getfa(v);
		if(a==b)
			if((dis(u)^dis(v))==0)
			{
				have_ans=1;
				break;
			}else;
		else
		{
			if(sz[a]>sz[b]) swap(a,b),swap(u,v);
			sz[b]+=sz[a],dist[a]=dist[u]^dist[v]^1;
			fa[a]=b;
			p.push_back((edge){a,b});
		}
	}
	if(!have_ans)
	{
		if(l==r) Answer[l]=1;
		else 
		{
			divide_(root<<1,l,mid);
			divide_(root<<1|1,mid+1,r);
		}
	}
	for(int i=p.size()-1;~i;--i)
	{
		int u=p[i].u,v=p[i].v;
		sz[v]-=sz[u];
		dist[u]=0,fa[u]=u;
	}
}
int main(int argc, char const *argv[])
{
	n=read(),m=read(),q=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		edge e=(edge){u,v};
		int l=read(),r=read();
		if(l<r) change(1,1,q,l+1,r,e);
	}
	for(int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
	divide_(1,1,q);
	for(int i=1;i<=q;++i)
		if(Answer[i]) puts("Yes");
		else puts("No");
	return 0;
}
-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------