graph / 二分图 /【模板】线段树分治
题目链接:luogu P5787
题目大意
有 n 个点,然后会加边删边,然后每次操作后问你这个图是否是二分图。
思路
首先加边删边,那边就会有存在的时间,所以你可以用一个线段树分治来搞。
那接着判断是否是二分图,可以用一个扩展域并查集来搞。
具体就是每个点 \(i\) 你在并查集上有两个点 \(i,i+n\)。
然后在图上你连边 \(x,y\),就是在并查集上连接 \(x,y+n\) 和 \(x+n,y\)。
然后如果 \(x,x+n\) 连通了,就说明不是二分图了。
因为 \(x+n\) 就是跟 \(x\) 连通的点,要染不同颜色的点,那连边就代表染不同颜色,那如果自己连了自己,就矛盾了,就不行了。
然后不难看出你就是在线段树上遍历,然后就要撤回并查集的操作。
那就不能路径压缩,而是要用按秩合并,然后你可以把合并的信息记录下来。
然后要撤回的时候你就把这些合并的信息拿出来,然后退回去就可以了。
代码
jzoj 版
#include<cstdio>
#include<vector>
using namespace std;
const int N = 300005;
int n, m, op, X, tmp, fa[N << 1];
int s[N], t[N], x[N], y[N], dg[N << 1];
struct XD_tree {
struct SSS {
int X, Y, add;
}sta[N << 2];
int l[N << 2], r[N << 2], lst[N << 2], tot;
vector <int> va[N << 2];
int find(int now) {//扩展域并查集
if (fa[now] == now) return now;
return find(fa[now]);
}
void connect(int x, int y, int now) {//因为要撤回,所以不能写路径压缩要写按秩合并
int X = find(x), Y = find(y);
if (dg[X] > dg[Y]) swap(X, Y);
sta[++tot] = (SSS){X, Y, dg[X] == dg[Y]};//记录,到时要撤回
fa[X] = Y;
if (dg[X] == dg[Y]) dg[Y]++;
}
void insert(int now, int l, int r, int L, int R, int val) {
if (L <= l && r <= R) {
va[now].push_back(val);
return ;
}
int mid = (l + r) >> 1;
if (L <= mid) insert(now << 1, l, mid, L, R, val);
if (mid < R) insert(now << 1 | 1, mid + 1, r, L, R, val);
}
void getans(int now, int l, int r) {
bool ans = 1; int lsttot = tot;
for (int i = 0; i < va[now].size(); i++) {
int XX = find(x[va[now][i]]), YY = find(y[va[now][i]]);
if (XX == YY) {//如果已经搜出没有,那范围内都是没有
for (int j = l; j <= r; j++) {
printf("NO\n");
}
ans = 0;
break;//不要直接return,还要撤回边
}
connect(x[va[now][i]], y[va[now][i]] + n, now);
connect(x[va[now][i]] + n, y[va[now][i]], now);
}
if (ans) {
if (l == r) {
printf("YES\n");
}
else {
int mid = (l + r) >> 1;
getans(now << 1, l, mid);
getans(now << 1 | 1, mid + 1, r);
}
}
while (tot > lsttot) {//撤回
dg[sta[tot].Y] -= sta[tot].add;
fa[sta[tot].X] = sta[tot].X;
tot--;
}
}
}T;
int main() {
// freopen("graph.in", "r", stdin);
// freopen("graph.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &op);
if (op == 1) {
tmp++;
scanf("%d %d", &x[tmp], &y[tmp]);
s[tmp] = i; t[tmp] = m;
}
else {
scanf("%d", &X); X++;
t[X] = i - 1;
}
}
for (int i = 1; i <= (n << 1); i++) fa[i] = i, dg[i] = 1;
for (int i = 1; i <= tmp; i++)
T.insert(1, 1, m, s[i], t[i], i);
T.getans(1, 1, m);
fclose(stdin);
fclose(stdout);
return 0;
}
luogu 版
#include<cstdio>
#include<vector>
using namespace std;
const int N = 300005;
int n, m, op, X, tmp, fa[N << 1], k;
int s[N], t[N], x[N], y[N], dg[N << 1];
struct XD_tree {
struct SSS {
int X, Y, add;
}sta[N << 2];
int l[N << 2], r[N << 2], lst[N << 2], tot;
vector <int> va[N << 2];
int find(int now) {
if (fa[now] == now) return now;
return find(fa[now]);
}
void connect(int x, int y, int now) {
int X = find(x), Y = find(y);
if (dg[X] > dg[Y]) swap(X, Y);
sta[++tot] = (SSS){X, Y, dg[X] == dg[Y]};
fa[X] = Y;
if (dg[X] == dg[Y]) dg[Y]++;
}
void insert(int now, int l, int r, int L, int R, int val) {
if (L <= l && r <= R) {
va[now].push_back(val);
return ;
}
int mid = (l + r) >> 1;
if (L <= mid) insert(now << 1, l, mid, L, R, val);
if (mid < R) insert(now << 1 | 1, mid + 1, r, L, R, val);
}
void getans(int now, int l, int r) {
bool ans = 1; int lsttot = tot;
for (int i = 0; i < va[now].size(); i++) {
int XX = find(x[va[now][i]]), YY = find(y[va[now][i]]);
if (XX == YY) {
for (int j = l; j <= r; j++) {
printf("No\n");
}
ans = 0;
break;
}
connect(x[va[now][i]], y[va[now][i]] + n, now);
connect(x[va[now][i]] + n, y[va[now][i]], now);
}
if (ans) {
if (l == r) {
printf("Yes\n");
}
else {
int mid = (l + r) >> 1;
getans(now << 1, l, mid);
getans(now << 1 | 1, mid + 1, r);
}
}
while (tot > lsttot) {
dg[sta[tot].Y] -= sta[tot].add;
fa[sta[tot].X] = sta[tot].X;
tot--;
}
}
}T;
int main() {
scanf("%d %d %d", &n, &k, &m);
for (int i = 1; i <= (n << 1); i++) fa[i] = i, dg[i] = 1;
for (int i = 1; i <= k; i++) {
scanf("%d %d %d %d", &x[i], &y[i], &s[i], &t[i]); s[i]++;
T.insert(1, 1, m, s[i], t[i], i);
}
T.getans(1, 1, m);
fclose(stdin);
fclose(stdout);
return 0;
}