Bipartite Checking (Codeforces 813F)
Tags: Others, dsu

You are given an undirected graph consisting of n vertices. Initially there are no edges in the graph. Also you are given q queries, each query either adds one undirected edge to the graph or removes it. After each query you have to check if the resulting graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color).

Input: The first line contains two integers n and q (2 ≤ n, q ≤ 100000).Then q lines follow. ith line contains two numbers xi and yi (1 ≤ xi < yi ≤ n). These numbers describe ith query: if there is an edge between vertices xi and yi, then remove it, otherwise add it.

Output: Print q lines. ith line must contain YES if the graph is bipartite after ith query, and NO otherwise.


Sample Inputs:
3 5
2 3
1 3
1 2
1 2
1 2

Sample Outputs:
YES
YES
NO
YES
NO

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_root1(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        ro0.append((i, root[i]))
        root[i] = s
    return s

def unite1(s, t):
    (rs, rt) = (get_root1(s), get_root1(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        ra0.append((rs, rank[rs]))
        rank[rs] += 1
    if rank[s] >= rank[t]:
        ro0.append((rt, root[rt]))
        root[rt] = rs
    else:
        ro0.append((rs, root[rs]))
        root[rs] = rt
    return

def same1(s, t):
    return True if get_root1(s) == get_root1(t) else False
(n, q) = map(int, input().split())
s = set()
m = 800
u = q // m + min(q % m, 1)
l = q
n2 = 2 * n + 1
ans = []
e = []
s1 = []
(ro0, ra0) = ([], [])
root = [i for i in range(n2)]
rank = [1 for _ in range(n2)]
for _ in range(u):
    s0 = set()
    z = []
    for _ in range(min(l, m)):
        (x, y) = map(int, input().split())
        z.append((x, y))
        if (x, y) in s:
            s.remove((x, y))
            s0.add((x, y))
    if len(ro0) + len(ra0) < q:
        while ro0:
            (i, c) = ro0.pop()
            root[i] = c
        while ra0:
            (i, c) = ra0.pop()
            rank[i] = c
    else:
        (ro0, ra0) = ([], [])
        root = [i for i in range(n2)]
        rank = [1 for _ in range(n2)]
    ok = 1
    for (x, y) in s:
        unite(x, y + n)
        unite(y, x + n)
        if same(x, x + n):
            ok = 0
            break
    if not ok:
        for (x, y) in s0:
            s.add((x, y))
        for (x, y) in z:
            if (x, y) in s:
                s.remove((x, y))
            else:
                s.add((x, y))
        ans.append('\n'.join(['NO'] * min(l, m)))
        l -= m
        continue
    cnt = 0
    for (x, y) in s0:
        e.append((x, y, len(ro0), len(ra0)))
        if same1(x, x + n):
            cnt -= 1
        if not same1(x, y + n):
            unite1(x, y + n)
            unite1(y, x + n)
        if same1(x, x + n):
            cnt += 1
        s.add((x, y))
    j = 0
    for (x, y) in z:
        j += 1
        if not (x, y) in s:
            e.append((x, y, len(ro0), len(ra0)))
            if same1(x, x + n):
                cnt -= 1
            if not same1(x, y + n):
                unite1(x, y + n)
                unite1(y, x + n)
            if same1(x, x + n):
                cnt += 1
            s.add((x, y))
        else:
            while e:
                (x0, y0, ro1, ra1) = e.pop()
                if not same1(x0, x0 + n):
                    cnt += 1
                while ro1 ^ len(ro0):
                    (i, c) = ro0.pop()
                    root[i] = c
                while ra1 ^ len(ra0):
                    (i, c) = ra0.pop()
                    rank[i] = c
                if not same1(x0, x0 + n):
                    cnt -= 1
                if x == x0 and y == y0:
                    break
                s1.append((x0, y0))
            while s1:
                (x0, y0) = s1.pop()
                e.append((x0, y0, len(ro0), len(ra0)))
                if same1(x0, x0 + n):
                    cnt -= 1
                if not same1(x0, y0 + n):
                    unite1(x0, y0 + n)
                    unite1(y0, x0 + n)
                if same1(x0, x0 + n):
                    cnt += 1
            s.remove((x, y))
        ans.append('YES' if not cnt else 'NO')
    l -= m
sys.stdout.write('\n'.join(ans))

Solution (Python):
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v, w):
    return (u * n2 + v) * n2 + w

def g(u, v):
    return u * n2 + v

def get_root(s):
    while s ^ root[s]:
        s = root[s]
    return s

def unite(s, t, i):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    (c1, c2, c3, c4) = (s, t, 0, root[t])
    if rank[s] == rank[t]:
        rank[s] += 1
        c3 = 1
    root[t] = s
    st1.append(f(c1, c2, c3))
    st2.append(g(i, c4))
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def undo(x, y):
    (s, z) = divmod(x, n2 * n2)
    (t, c) = divmod(z, n2)
    rt = y % n2
    rank[s] -= c
    root[t] = rt
    return
(n, q) = map(int, input().split())
d = defaultdict(lambda : -1)
(u, v) = ([], [])
(x, y) = ([0] * q, [0] * q)
for i in range(q):
    (x0, y0) = map(int, input().split())
    if x0 > y0:
        (x0, y0) = (y0, x0)
    (x[i], y[i]) = (x0, y0)
    if d[x0, y0] == -1:
        d[x0, y0] = i
    else:
        u.append(d[x0, y0])
        v.append(i - 1)
        d[x0, y0] = -1
for i in d.values():
    if i ^ -1:
        u.append(i)
        v.append(q - 1)
l1 = pow(2, (q + 1).bit_length())
l2 = 2 * l1
s0 = [0] * l2
for (u0, v0) in zip(u, v):
    l0 = u0 + l1
    r0 = v0 + l1
    while l0 <= r0:
        if l0 & 1:
            s0[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            s0[r0] += 1
            r0 -= 1
        r0 >>= 1
for i in range(1, l2):
    s0[i] += s0[i - 1]
now = [0] + list(s0)
tree = [-1] * now[l2]
m = len(u)
for i in range(m):
    l0 = u[i] + l1
    r0 = v[i] + l1
    while l0 <= r0:
        if l0 & 1:
            tree[now[l0]] = u[i]
            now[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            tree[now[r0]] = u[i]
            now[r0] += 1
            r0 -= 1
        r0 >>= 1
n += 5
n2 = 2 * n
root = [i for i in range(n2)]
rank = [1 for _ in range(n2)]
s0 = [0] + s0
(st1, st2) = ([], [])
now = 1
ng = 0
for i in range(s0[1], s0[2]):
    j = tree[i]
    (u0, v0) = (get_root(x[j]), get_root(y[j]))
    (u1, v1) = (get_root(x[j] + n), get_root(y[j] + n))
    if u0 == v0 and u0 == v1:
        continue
    if u0 == u1:
        ng -= 1
    if v0 == v1:
        ng -= 1
    unite(u0, v1, 1)
    unite(u1, v0, 1)
    if same(u0, u1):
        ng += 1
visit = [0] * l2
cnt = [0] * l2
cnt[1] = ng
ans = []
while len(ans) ^ q:
    if now >= l1:
        ans.append('YES' if not ng else 'NO')
    if now >= l1 or visit[now << 1 ^ 1]:
        visit[now] = 1
        while st1 and st2[-1] // n2 == now:
            undo(st1.pop(), st2.pop())
        now >>= 1
        ng = cnt[now]
        continue
    now = now << 1 if not visit[now << 1] else now << 1 ^ 1
    for i in range(s0[now], s0[now + 1]):
        j = tree[i]
        (u0, v0) = (get_root(x[j]), get_root(y[j]))
        (u1, v1) = (get_root(x[j] + n), get_root(y[j] + n))
        if u0 == v0 and u0 == v1:
            continue
        if u0 == u1:
            ng -= 1
        if v0 == v1:
            ng -= 1
        unite(u0, v1, now)
        unite(u1, v0, now)
        if same(u0, u1):
            ng += 1
    cnt[now] = ng
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v, w):
    return (u * n2 + v) * n2 + w

def g(u, v):
    return u * n2 + v

def get_root(s):
    while s ^ root[s]:
        s = root[s]
    return s

def unite(s, t, i):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    (c1, c2, c3, c4) = (s, t, 0, root[t])
    if rank[s] == rank[t]:
        rank[s] += 1
        c3 = 1
    root[t] = s
    st1.append(f(c1, c2, c3))
    st2.append(g(i, c4))
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def undo(x, y):
    (s, z) = divmod(x, n2 * n2)
    (t, c) = divmod(z, n2)
    rt = y % n2
    rank[s] -= c
    root[t] = rt
    return
(n, q) = map(int, input().split())
d = defaultdict(lambda : -1)
(u, v) = ([], [])
(x, y) = ([0] * q, [0] * q)
for i in range(q):
    (x0, y0) = map(int, input().split())
    if x0 > y0:
        (x0, y0) = (y0, x0)
    (x[i], y[i]) = (x0, y0)
    if d[x0, y0] == -1:
        d[x0, y0] = i
    else:
        u.append(d[x0, y0])
        v.append(i - 1)
        d[x0, y0] = -1
for i in d.values():
    if i ^ -1:
        u.append(i)
        v.append(q - 1)
l1 = pow(2, (q + 1).bit_length())
l2 = 2 * l1
s0 = [0] * l2
for (u0, v0) in zip(u, v):
    l0 = u0 + l1
    r0 = v0 + l1
    while l0 <= r0:
        if l0 & 1:
            s0[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            s0[r0] += 1
            r0 -= 1
        r0 >>= 1
for i in range(1, l2):
    s0[i] += s0[i - 1]
now = [0] + list(s0)
tree = [-1] * now[l2]
m = len(u)
for i in range(m):
    l0 = u[i] + l1
    r0 = v[i] + l1
    while l0 <= r0:
        if l0 & 1:
            tree[now[l0]] = u[i]
            now[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            tree[now[r0]] = u[i]
            now[r0] += 1
            r0 -= 1
        r0 >>= 1
n += 5
n2 = 2 * n
root = [i for i in range(n2)]
rank = [1 for _ in range(n2)]
s0 = [0] + s0
(st1, st2) = ([], [])
now = 1
ng = 0
for i in range(s0[1], s0[2]):
    j = tree[i]
    (u0, v0) = (get_root(x[j]), get_root(y[j]))
    (u1, v1) = (get_root(x[j] + n), get_root(y[j] + n))
    if u0 == v0 and u0 == v1:
        continue
    if u0 == u1:
        ng -= 1
    if v0 == v1:
        ng -= 1
    unite(u0, v1, 1)
    unite(u1, v0, 1)
    if same(u0, u1):
        ng += 1
visit = [0] * l2
cnt = [0] * l2
cnt[1] = ng
ans = []
while len(ans) ^ q:
    if now >= l1:
        ans.append('YES' if not ng else 'NO')
    if now >= l1 or visit[now << 1 ^ 1]:
        visit[now] = 1
        while st1 and st2[-1] // n2 == now:
            undo(st1.pop(), st2.pop())
        now >>= 1
        ng = cnt[now]
        continue
    now = now << 1 if not visit[now << 1] else now << 1 ^ 1
    for i in range(s0[now], s0[now + 1]):
        j = tree[i]
        (u0, v0) = (get_root(x[j]), get_root(y[j]))
        (u1, v1) = (get_root(x[j] + n), get_root(y[j] + n))
        if u0 == v0 and u0 == v1:
            continue
        if u0 == u1:
            ng -= 1
        if v0 == v1:
            ng -= 1
        unite(u0, v1, now)
        unite(u1, v0, now)
        if same(u0, u1):
            ng += 1
    cnt[now] = ng
sys.stdout.write('\n'.join(map(str, ans)))