AND-MEX Walk (Codeforces 1659E)
Tags: Others, dsu

There is an undirected, connected graph with $$$n$$$ vertices and $$$m$$$ weighted edges. A walk from vertex $$$u$$$ to vertex $$$v$$$ is defined as a sequence of vertices $$$p_1,p_2,\ldots,p_k$$$ (which are not necessarily distinct) starting with $$$u$$$ and ending with $$$v$$$, such that $$$p_i$$$ and $$$p_{i+1}$$$ are connected by an edge for $$$1 \leq i < k$$$.We define the length of a walk as follows: take the ordered sequence of edges and write down the weights on each of them in an array. Now, write down the bitwise AND of every nonempty prefix of this array. The length of the walk is the MEX of all these values.More formally, let us have $$$[w_1,w_2,\ldots,w_{k-1}]$$$ where $$$w_i$$$ is the weight of the edge between $$$p_i$$$ and $$$p_{i+1}$$$. Then the length of the walk is given by $$$\mathrm{MEX}(\{w_1,\,w_1\& w_2,\,\ldots,\,w_1\& w_2\& \ldots\& w_{k-1}\})$$$, where $$$\&$$$ denotes the bitwise AND operation.Now you must process $$$q$$$ queries of the form u v. For each query, find the minimum possible length of a walk from $$$u$$$ to $$$v$$$.The MEX (minimum excluded) of a set is the smallest non-negative integer that does not belong to the set. For instance:   The MEX of $$$\{2,1\}$$$ is $$$0$$$, because $$$0$$$ does not belong to the set.  The MEX of $$$\{3,1,0\}$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the set, but $$$2$$$ does not.  The MEX of $$$\{0,3,1,2\}$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the set, but $$$4$$$ does not. 

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$; $$$n-1 \leq m \leq \min{\left(\frac{n(n-1)}{2},10^5\right)}$$$).Each of the next $$$m$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$w$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$; $$$0 \leq w < 2^{30}$$$) indicating an undirected edge between vertex $$$a$$$ and vertex $$$b$$$ with weight $$$w$$$. The input will not contain self-loops or duplicate edges, and the provided graph will be connected.The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$).Each of the next $$$q$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), the description of each query.

Output: For each query, print one line containing a single integer — the answer to the query.

Note: The following is an explanation of the first example.  The graph in the first example. Here is one possible walk for the first query:$$$$$$1 \overset{5}{\rightarrow} 3 \overset{3}{\rightarrow} 2 \overset{1}{\rightarrow} 1 \overset{5}{\rightarrow} 3 \overset{1}{\rightarrow} 4 \overset{2}{\rightarrow} 5.$$$$$$The array of weights is $$$w=[5,3,1,5,1,2]$$$. Now if we take the bitwise AND of every prefix of this array, we get the set $$$\{5,1,0\}$$$. The MEX of this set is $$$2$$$. We cannot get a walk with a smaller length (as defined in the statement).

Sample Inputs:
6 7
1 2 1
2 3 3
3 1 5
4 5 2
5 6 4
6 4 6
3 4 1
3
1 5
1 2
5 3

9 8
1 2 5
2 3 11
3 4 10
3 5 10
5 6 2
5 7 1
7 8 5
7 9 5
10
5 7
2 5
7 1
6 4
5 2
7 6
4 1
6 2
4 7
2 8

Sample Outputs:
2
0
1

0
0
2
0
0
2
1
0
1
1

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

def main(t):
    D = 32
    (n, m) = map(int, input().split())
    edges = []
    evens = [False] * n
    for _ in range(m):
        (u, v, w) = map(int, input().split())
        edges.append([u - 1, v - 1, w])
        if w % 2 == 0:
            evens[u - 1] = True
            evens[v - 1] = True
    group = [[j for j in range(n)] for i in range(D)]

    def unionfind(root, d):
        son = root
        while root != group[d][root]:
            root = group[d][root]
        while son != root:
            temp = group[d][son]
            group[d][son] = root
            son = group[d][temp]
        return root
    for [u, v, w] in edges:
        for d in range(D):
            if 1 << d & w == 0:
                continue
            rootu = unionfind(u, d)
            rootv = unionfind(v, d)
            if rootu == rootv:
                continue
            group[d][max(rootu, rootv)] = group[d][min(rootu, rootv)]
    collect = [False for _ in range(D * n)]
    for d in range(D):
        for i in range(n):
            group[d][i] = unionfind(i, d)
    for d in range(1, D):
        for i in range(n):
            index = d * n + group[d][i]
            if evens[i]:
                collect[index] = True
    q = int(input())
    for test in range(q):
        (u, v) = map(int, input().split())
        u -= 1
        v -= 1
        (flag1, flag2) = (False, False)
        for d in range(D):
            if group[d][u] == group[d][v]:
                flag1 = True
                break
            if collect[d * n + group[d][u]]:
                flag2 = True
        if flag1:
            print(0)
        elif flag2:
            print(1)
        else:
            print(2)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
from collections import defaultdict
MAX_BIT = 30

class DisjointSet:

    def __init__(self, n: int=0) -> None:
        self.parent_or_size = [-1] * n
        self.has_even = [False] * n

    def union(self, a: int, b: int) -> int:
        x = self.find(a)
        y = self.find(b)
        if x == y:
            return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            (x, y) = (y, x)
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def find(self, a: int) -> int:
        parent = self.parent_or_size[a]
        while parent >= 0:
            if self.parent_or_size[parent] < 0:
                return parent
            (self.parent_or_size[a], a, parent) = (self.parent_or_size[parent], self.parent_or_size[parent], self.parent_or_size[self.parent_or_size[parent]])
        return a

def reader():
    while True:
        x = sys.stdin.readline()
        yield x.strip()

def make_input(lines):
    x = iter(lines)
    return lambda : next(x)

def pp(lines):
    input = make_input(lines)
    (n, m) = map(int, input().split())
    has_even_edge = [False] * (n + 1)
    DSU = [DisjointSet(n + 1) for _ in range(MAX_BIT)]
    for _ in range(m):
        (e1, e2, w) = map(int, input().split())
        for i in range(MAX_BIT):
            if 1 << i > w:
                break
            if w & 1 << i:
                DSU[i].union(e1, e2)
        if w % 2 == 0:
            has_even_edge[e1] = True
            has_even_edge[e2] = True
    nodes_with_even_edges = []
    not_yet_reach_even = set()
    for (idx, k) in enumerate(has_even_edge):
        if k:
            nodes_with_even_edges.append(idx)
        elif idx > 0:
            not_yet_reach_even.add(idx)
    for i in range(1, MAX_BIT):
        valid_parents = set()
        for node in nodes_with_even_edges:
            valid_parents.add(DSU[i].find(node))
        to_remove = set()
        for node in not_yet_reach_even:
            if DSU[i].find(node) in valid_parents:
                to_remove.add(node)
        not_yet_reach_even -= to_remove
        if not not_yet_reach_even:
            break
    ans = []

    def process_query(n1, n2):
        for i in range(MAX_BIT):
            if DSU[i].find(n1) == DSU[i].find(n2):
                return 0
        if n1 in not_yet_reach_even:
            return 2
        else:
            return 1
    for _ in range(int(input())):
        (n1, n2) = map(int, input().split())
        ans.append(process_query(n1, n2))
    print(' '.join(map(str, ans)))
x = '9 8\n1 2 5\n2 3 11\n3 4 10\n3 5 10\n5 6 2\n5 7 1\n7 8 5\n7 9 5\n10\n5 7\n2 5\n7 1\n6 4\n5 2\n7 6\n4 1\n6 2\n4 7\n2 8'
if 'pekka' in sys.argv[0] or sys.argv[0].endswith('pydevconsole.py'):
    pp(x.split('\n'))
else:
    pp(reader())

Solution (Python):
from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))

class dsu:

    def __init__(self, n):
        self.p = [0] * (n + 1)
        self.rank = [0] * (n + 1)
        for i in range(1, n + 1):
            self.p[i] = i

    def find(self, node):
        if self.p[node] == node:
            return node
        self.p[node] = self.find(self.p[node])
        return self.p[node]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if self.rank[u] == self.rank[v]:
            self.p[v] = u
            self.rank[u] += 1
        elif self.rank[u] > self.rank[v]:
            self.p[v] = u
        else:
            self.p[u] = v

def answer():
    zeronotset = [False for i in range(n + 1)]
    for i in range(m):
        (u, v, w) = edges[i]
        if w & 1 == 0:
            zeronotset[u] = True
            zeronotset[v] = True
    d = [dsu(n) for i in range(30)]
    for i in range(30):
        for j in range(m):
            (u, v, w) = edges[j]
            if w >> i & 1:
                d[i].union(u, v)
    zero = [dsu(n) for i in range(30)]
    for i in range(1, 30):
        for j in range(m):
            (u, v, w) = edges[j]
            if w & 1 and w >> i & 1:
                zero[i].union(u, v)
    value = [[2 for i in range(n + 1)] for i in range(30)]
    for i in range(1, 30):
        for j in range(m):
            (u, v, w) = edges[j]
            if zeronotset[u]:
                value[i][zero[i].find(u)] = 1
            if zeronotset[v]:
                value[i][zero[i].find(v)] = 1
    for q in range(int(input())):
        (u, v) = inp()
        ans = 2
        for i in range(30):
            if d[i].find(u) == d[i].find(v):
                ans = 0
                break
        if ans == 2:
            for i in range(1, 30):
                if value[i][zero[i].find(u)] == 1:
                    ans = 1
                    break
        print(ans)
for T in range(1):
    (n, m) = inp()
    edges = []
    for i in range(m):
        (u, v, w) = inp()
        edges.append([u, v, w])
    answer()