MinOr Tree (Codeforces 1624G)
Tags: Greedy, dsu

Recently, Vlad has been carried away by spanning trees, so his friends, without hesitation, gave him a connected weighted undirected graph of $$$n$$$ vertices and $$$m$$$ edges for his birthday.Vlad defined the ority of a spanning tree as the bitwise OR of all its weights, and now he is interested in what is the minimum possible ority that can be achieved by choosing a certain spanning tree. A spanning tree is a connected subgraph of a given graph that does not contain cycles.In other words, you want to keep $$$n-1$$$ edges so that the graph remains connected and the bitwise OR weights of the edges are as small as possible. You have to find the minimum bitwise OR itself.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input.An empty line is written in front of each test case.This is followed by two numbers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges of the graph, respectively.The next $$$m$$$ lines contain the description of the edges. Line $$$i$$$ contains three numbers $$$v_i$$$, $$$u_i$$$ and $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$v_i \neq u_i$$$) — the vertices that the edge connects and its weight.It is guaranteed that the sum $$$m$$$ and the sum $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and each test case contains a connected graph.

Output: Print $$$t$$$ lines, each of which contains the answer to the corresponding set of input data — the minimum possible spanning tree ority.

Note:   Graph from the first test case.   Ority of this tree equals to 2 or 2 = 2 and it's minimal.   Without excluding edge with weight $$$1$$$ ority is 1 or 2 = 3. 

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

Sample Outputs:
2
10
3

Solution (Python):
import sys
input = sys.stdin.buffer.readline
uf = None
seq = [None] * 50000

def is_connected(edges, mask):
    for x in range(N):
        uf[x] = x

    def find(x):
        if x == uf[x]:
            return x
        else:
            pos = 0
            seq[pos] = x
            pos += 1
            while uf[x] != x:
                x = uf[x]
                seq[pos] = x
                pos += 1
            for i in range(pos):
                uf[seq[i]] = seq[pos - 1]
            return x
    nc = N
    for (fr, to, w) in edges:
        if not w & mask:
            px = find(fr)
            py = find(to)
            if px != py:
                nc -= 1
            uf[py] = px
    return nc == 1
T = int(input())
for _ in range(T):
    input()
    (N, M) = map(int, input().split())
    uf = list(range(N))
    edges = []
    for _ in range(M):
        (fro, to, weight) = map(int, input().split())
        fro -= 1
        to -= 1
        edges.append((fro, to, weight))
    ANSWER = 0
    FORBIDDEN = 0
    for bit in range(29, -1, -1):
        if is_connected(edges, FORBIDDEN | 1 << bit):
            FORBIDDEN |= 1 << bit
        else:
            ANSWER |= 1 << bit
    print(ANSWER)

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

def unionfind(group, root):
    son = root
    while group[root] != root:
        root = group[root]
    while son != root:
        temp = group[son]
        group[son] = root
        son = group[temp]
    return root

def detect(edges, cannot, n):
    group = [i for i in range(n)]
    rest = n - 1
    for [i, j, w] in edges:
        if w & cannot > 0:
            continue
        rooti = unionfind(group, i)
        rootj = unionfind(group, j)
        if rooti == rootj:
            continue
        group[max(rooti, rootj)] = min(rooti, rootj)
        rest -= 1
    if rest == 0:
        output = True
    else:
        output = False
    return output

def main(t):
    s = input()
    (n, m) = map(int, input().split())
    edges = []
    for _ in range(m):
        (u, v, w) = map(int, input().split())
        edges.append([u - 1, v - 1, w])
    cannot = 0
    for d in range(30, -1, -1):
        if detect(edges, cannot + (1 << d), n):
            cannot += 1 << d
    ans = (1 << 31) - 1 - cannot
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n

    def Find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.Find(self.par[x])
            return self.par[x]

    def Unite(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def Same(self, x, y):
        return self.Find(x) == self.Find(y)

    def Size(self, x):
        return -self.par[self.Find(x)]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
    t = int(input())
    for _ in range(t):
        __ = input()
        (n, m) = map(int, input().split())
        E = []
        for i in range(m):
            (u, v, w) = map(int, input().split())
            (u, v) = (u - 1, v - 1)
            E.append((u, v, w))
        ng = 0
        ans = 0
        for b in reversed(range(30)):
            uf = UnionFind(n)
            for (u, v, w) in E:
                if ng & w != 0:
                    continue
                if 1 << b & w != 0:
                    continue
                uf.Unite(u, v)
            if uf.Size(0) == n:
                ng |= 1 << b
            else:
                ans += 1 << b
        print(ans)
if __name__ == '__main__':
    main()