[bzoj4025] 二分图

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) 。

数据范围：
(n leq 100000)，(m leq 200000)，(T leq 100000) ，(1 leq u,v leq n)，(0 leq start leq end leq T)。

---

想法

首先，如何判断二分图是个问题【思考】
给出结论——点数 (geq 2) 且没有奇环。
想一下感觉挺对的，也就是说任意两个点间路径长度的奇偶性是一样的，偶数则两个点在同一“集合”，奇数则在不同“集合”

那么我们可以维护一棵树，加边时若这两个点已经联通，判断一下当前两点间距离是不是奇数，若不是，则加边后不是二分图。

但是这道题不光有加边，还有删边。
那么就有两种做法，(LCT) 或线段树分治。

做法一：LCT

动态维护生成树咯。
将所有边按时间依次加入。
若没出现环则直接连边
若出现环：若是奇环，标记从当前时间到环上的最早删除时间“不是二分图”，偶环不用标记。删除环上删除时间最小的边。
删边操作，若该边已被删则不管，没被删就删掉。
（然而我只是口胡，并没写这个做法。。。）

做法二：线段树分治

以时间为下标建线段树，每条边在它存在的时间范围上打标记。
遍历线段树每个结点，用并查集维护“那棵树”，只需维护每个点到它所在的并查集树根的路径的奇偶性就行了。
注意：
1.在线段树某个节点发现“不是二分图”，直接标记它代表的区间的所有时间点“不是二分图”，不用再往下递归了。
2.由于要“往回退”，即并查集要删边，所以不能路径压缩。

不用路径压缩的并查集，每次找 (fa) 是 (O(logn)) 的，每个点要找 (O(logn)) 次，所以总复杂度 (O(nlog^2n))

---

代码

(WA) 了好久好久好久好久……
只见我 (WA) 地一声哭出来呜呜呜……

复制代码#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; int read(){ int x=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x; } const int N = 100005; int n,m,T; struct edge{ int u,v; }d[N*2]; int tot; int root,cnt,ch[N*2][2]; vector<edge> seg[N*2]; void build(int x,int l,int r){ if(l==r) return; int mid=(l+r)>>1; build(ch[x][0]=++cnt,l,mid); build(ch[x][1]=++cnt,mid+1,r); } void ins(int x,int l,int r,int L,int R,int c){ if(l==L && r==R) { seg[x].push_back(d[c]); return; } int mid=(l+r)>>1; if(R<=mid) ins(ch[x][0],l,mid,L,R,c); else if(L>mid) ins(ch[x][1],mid+1,r,L,R,c); else{ ins(ch[x][0],l,mid,L,mid,c); ins(ch[x][1],mid+1,r,mid+1,R,c); } } int ans[N],fa[N],val[N],pre[N],sz[N]; int getfa(int x) { if(x==fa[x]) return x; int z=getfa(fa[x]); val[x]=val[fa[x]]^pre[x]; return z; } void work(int x,int l,int r){ int flag=1; vector<edge> opt; for(int i=0;i<seg[x].size();i++){ int fu=getfa(seg[x][i].u),fv=getfa(seg[x][i].v); if(fu==fv){ if(val[seg[x][i].u]==val[seg[x][i].v]) flag=0; } else{ if(sz[fu]>sz[fv]) swap(fu,fv); fa[fu]=fv; sz[fv]+=sz[fu]; pre[fu]=val[seg[x][i].u]^val[seg[x][i].v]^1; opt.push_back((edge){fu,fv}); } } if(l<r && flag){ int mid=(l+r)>>1; work(ch[x][0],l,mid); work(ch[x][1],mid+1,r); } if(l==r) ans[l]=flag; for(int i=opt.size()-1;i>=0;i--){ pre[opt[i].u]=val[opt[i].u]=0; //别忘了把 val 也清零！ sz[opt[i].v]-=sz[opt[i].u]; fa[opt[i].u]=opt[i].u; } } int main() { int u,v,st,ed; n=read(); m=read(); T=read(); build(root=++cnt,1,T); while(m--){ u=read(); v=read(); st=read()+1; ed=read()+1; if(st==ed) continue; d[++tot]=(edge){u,v}; ins(root,1,T,st,ed-1,tot); } for(int i=1;i<=n;i++) fa[i]=i,val[i]=pre[i]=0,sz[i]=1; work(root,1,T); for(int i=1;i<=T;i++) if(ans[i]) printf("Yesn"); else printf("Non"); return 0; }

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 100005;
int n,m,T;
struct edge{ int u,v; }d[N*2];
int tot;
int root,cnt,ch[N*2][2];
vector<edge> seg[N*2];
void build(int x,int l,int r){
if(l==r) return;
int mid=(l+r)>>1;
build(ch[x][0]=++cnt,l,mid);
build(ch[x][1]=++cnt,mid+1,r);
}
void ins(int x,int l,int r,int L,int R,int c){
if(l==L && r==R) { seg[x].push_back(d[c]); return; }
int mid=(l+r)>>1;
if(R<=mid) ins(ch[x][0],l,mid,L,R,c);
else if(L>mid) ins(ch[x][1],mid+1,r,L,R,c);
else{
ins(ch[x][0],l,mid,L,mid,c);
ins(ch[x][1],mid+1,r,mid+1,R,c);
}
}
int ans[N],fa[N],val[N],pre[N],sz[N];
int getfa(int x) {
if(x==fa[x]) return x;
int z=getfa(fa[x]);
val[x]=val[fa[x]]^pre[x];
return z;
}
void work(int x,int l,int r){
int flag=1;
vector<edge> opt;
for(int i=0;i<seg[x].size();i++){
int fu=getfa(seg[x][i].u),fv=getfa(seg[x][i].v);
if(fu==fv){
if(val[seg[x][i].u]==val[seg[x][i].v]) flag=0;
}
else{
if(sz[fu]>sz[fv]) swap(fu,fv);
fa[fu]=fv; sz[fv]+=sz[fu];
pre[fu]=val[seg[x][i].u]^val[seg[x][i].v]^1;
opt.push_back((edge){fu,fv});
}
}
if(l<r && flag){
int mid=(l+r)>>1;
work(ch[x][0],l,mid);
work(ch[x][1],mid+1,r);
}
if(l==r) ans[l]=flag;
for(int i=opt.size()-1;i>=0;i--){
pre[opt[i].u]=val[opt[i].u]=0; //别忘了把 val 也清零！
sz[opt[i].v]-=sz[opt[i].u];
fa[opt[i].u]=opt[i].u;
}
}
int main()
{
int u,v,st,ed;
n=read(); m=read(); T=read();
build(root=++cnt,1,T);
while(m--){
u=read(); v=read(); st=read()+1; ed=read()+1;
if(st==ed) continue;
d[++tot]=(edge){u,v};
ins(root,1,T,st,ed-1,tot);
}
for(int i=1;i<=n;i++) fa[i]=i,val[i]=pre[i]=0,sz[i]=1;
work(root,1,T);
for(int i=1;i<=T;i++)
if(ans[i]) printf("Yesn");
else printf("Non");
return 0;
}