首页 > 代码库 > bzoj4025 二分图
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
1 2 0 2
2 3 0 3
1 3 1 2
Sample Output
Yes
No
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<=100000，m<=200000，T<=100000，1<=u,v<=n，0<=start<=end<=T。
正解：$CDQ$分治+并查集。
这类题都是一个套路。把在区间$[l,r]$内恒出现的边连起来，然后使用带权并查集判断是否为奇环即可。
注意连边的一些细节，比如说点权需要改成$dep[u] \ xor \ dep[v] \ xor 1$，还有就是撤回的时候连上去的那个点深度设为$0$。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define N (500010)15 #define ls (x<<1)16 #define rs (x<<1|1)17 #define il inline18 #define RG register19 #define ll long long20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)21 22 using namespace std;23 24 struct node{ int x,y,a,h; }st[20000010];25 struct edge{ int u,v; }g[N];26 27 vector <int> mp[4*N];28 29 int h[N],a[N],dep[N],fa[N],sz[4*N],n,m,T,cnt,top;30 31 il int gi(){32 RG int x=0,q=1; RG char ch=getchar();33 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();34 if (ch==‘-‘) q=-1,ch=getchar();35 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();36 return q*x;37 }38 39 il void query(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int v){40 if (xl<=l && r<=xr){ ++sz[x],mp[x].push_back(v); return; } RG int mid=(l+r)>>1;41 if (xr<=mid) query(ls,l,mid,xl,xr,v);42 else if (xl>mid) query(rs,mid+1,r,xl,xr,v);43 else query(ls,l,mid,xl,mid,v),query(rs,mid+1,r,mid+1,xr,v); return;44 }45 46 il int find(RG int x){47 if (fa[x]==x) return x; RG int y=find(fa[x]);48 dep[x]=dep[fa[x]]^a[x]; return y;49 }50 51 il int unionn(RG int u,RG int v){52 RG int x=find(u),y=find(v); if (h[x]>h[y]) swap(x,y),swap(u,v);53 if (x==y) return dep[u]^dep[v]^1; st[++top]=(node){x,y,a[x],h[y]};54 fa[x]=y,a[x]=dep[u]^dep[v]^1; if (h[x]==h[y]) ++h[y]; return 0;55 }56 57 il void del(RG int now){58 for (;top>now;--top){59 fa[st[top].x]=st[top].x,dep[st[top].x]=0;60 a[st[top].x]=st[top].a,h[st[top].y]=st[top].h;61 }62 return;63 }64 65 il void solve(RG int x,RG int l,RG int r){66 RG int mid=(l+r)>>1,now=top;67 for (RG int i=0,j,res;i<sz[x];++i){68 j=mp[x][i],res=unionn(g[j].u,g[j].v);69 if (res){ for (RG int i=l;i<=r;++i) puts("No"); del(now); return; }70 }71 if (l==r){ puts("Yes"),del(now); return; }72 solve(ls,l,mid),solve(rs,mid+1,r),del(now); return;73 }74 75 il void work(){76 n=gi(),m=gi(),T=gi(); for (RG int i=1;i<=n;++i) fa[i]=i,h[i]=a[i]=1;77 for (RG int i=1,u,v,l,r;i<=m;++i){78 u=gi(),v=gi(),l=gi()+1,r=gi(); if (l>r) continue;79 g[++cnt].u=u,g[cnt].v=v,query(1,1,T,l,r,cnt);80 }81 solve(1,1,T); return;82 }83 84 int main(){85 File("grape");86 work();87 return 0;88 }
bzoj4025 二分图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。