DFS Trees (Codeforces 1707C)
Tags: Greedy, dsu

You are given a connected undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The weight of the $$$i$$$-th edge is $$$i$$$.Here is a wrong algorithm of finding a minimum spanning tree (MST) of a graph:vis := an array of length ns := a set of edgesfunction dfs(u):    vis[u] := true    iterate through each edge (u, v) in the order from smallest to largest edge weight        if vis[v] = false            add edge (u, v) into the set (s)            dfs(v)function findMST(u):    reset all elements of (vis) to false    reset the edge set (s) to empty    dfs(u)    return the edge set (s)Each of the calls findMST(1), findMST(2), ..., findMST(n) gives you a spanning tree of the graph. Determine which of these trees are minimum spanning trees.

Input: The first line of the input contains two integers $$$n$$$, $$$m$$$ ($$$2\le n\le 10^5$$$, $$$n-1\le m\le 2\cdot 10^5$$$) — the number of vertices and the number of edges in the graph.Each of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i, v_i\le n$$$, $$$u_i\ne v_i$$$), describing an undirected edge $$$(u_i,v_i)$$$ in the graph. The $$$i$$$-th edge in the input has weight $$$i$$$.It is guaranteed that the graph is connected and there is at most one edge between any pair of vertices.

Output: You need to output a binary string $$$s$$$, where $$$s_i=1$$$ if findMST(i) creates an MST, and $$$s_i = 0$$$ otherwise.

Note: Here is the graph given in the first example.  There is only one minimum spanning tree in this graph. A minimum spanning tree is $$$(1,2),(3,5),(1,3),(2,4)$$$ which has weight $$$1+2+3+5=11$$$.Here is a part of the process of calling findMST(1):  reset the array vis and the edge set s;  calling dfs(1);  vis[1] := true;  iterate through each edge $$$(1,2),(1,3)$$$;  add edge $$$(1,2)$$$ into the edge set s, calling dfs(2):   vis[2] := true  iterate through each edge $$$(2,1),(2,3),(2,4)$$$;  because vis[1] = true, ignore the edge $$$(2,1)$$$;  add edge $$$(2,3)$$$ into the edge set s, calling dfs(3):   ...   In the end, it will select edges $$$(1,2),(2,3),(3,5),(2,4)$$$ with total weight $$$1+4+2+5=12>11$$$, so findMST(1) does not find a minimum spanning tree.It can be shown that the other trees are all MSTs, so the answer is 01111.

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

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

Sample Outputs:
01111

0011111011

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):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    return

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

def get_size(s):
    return size[get_root(s)]

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in x:
        s[i + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (q, dist, parent)

def f(u, v):
    return u * (n + 1) + v
(n, m) = map(int, input().split())
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
(x, y) = ([], [])
for _ in range(m):
    (u, v) = map(int, input().split())
    if not same(u, v):
        unite(u, v)
        x.append(u)
        x.append(v)
    else:
        y.append(u)
        y.append(v)
(G, s0) = make_graph(n, n - 1)
inf = pow(10, 9) + 1
(p, dist, parent) = bfs(1)
l = (n + 1).bit_length()
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
dp0 = [0] * ((n + 1) * l)
for i in range(2, n + 1):
    dp0[i] = parent[i]
for i in range(1, l):
    for j in range(2, n + 1):
        dp0[f(i, j)] = dp0[f(i - 1, dp0[f(i - 1, j)])]
dp = [0] * (n + 1)
m = len(y) // 2
for i in range(m):
    (u, v) = (y[2 * i], y[2 * i + 1])
    if dist[u] < dist[v]:
        (u, v) = (v, u)
    w = u
    (d, i) = (dist[u] - dist[v] - 1, 0)
    while d > 0:
        if not d & pow2[i]:
            i += 1
            continue
        w = dp0[f(i, w)]
        d ^= pow2[i]
    if dist[w] ^ dist[v] and parent[w] == v:
        dp[1] += 1
        dp[w] -= 1
        dp[u] += 1
    else:
        dp[u] += 1
        dp[v] += 1
for i in p[1:]:
    dp[i] += dp[parent[i]]
ans = ['1' if dp[i] == m else '0' for i in range(1, n + 1)]
sys.stdout.write(''.join(ans))

Solution (Python):
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
EDGE = [tuple(map(int, input().split())) for i in range(m)]
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)
USE = [0] * m
for i in range(m):
    (x, y) = EDGE[i]
    if find(x) == find(y):
        USE[i] = 0
    else:
        USE[i] = 1
        Union(x, y)
E = [[] for i in range(n + 1)]
OK = [0] * (n + 1)
for i in range(m):
    if USE[i] == 1:
        (x, y) = EDGE[i]
        E[x].append(y)
        E[y].append(x)
        OK[x] = 1
        OK[y] = 1
N = n + 1
ROOT = 1
QUE = [ROOT]
Parent = [-1] * (N + 1)
Height = [-1] * (N + 1)
Parent[ROOT] = N
Height[ROOT] = 0
Child = [[] for i in range(N + 1)]
TOP_SORT = []
while QUE:
    x = QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to] == -1:
            Parent[to] = x
            Height[to] = Height[x] + 1
            Child[x].append(to)
            QUE.append(to)
Children = [1] * (N + 1)
for x in TOP_SORT[::-1]:
    Children[Parent[x]] += Children[x]
USE = [0] * N
Group = [i for i in range(N)]
for x in TOP_SORT:
    USE[x] = 1
    MAX_children = 0
    select_node = 0
    for to in E[x]:
        if USE[to] == 0 and Children[to] > MAX_children:
            select_node = to
            MAX_children = Children[to]
    for to in E[x]:
        if USE[to] == 0 and to == select_node:
            Group[to] = Group[x]

def LCA(a, b):
    while Group[a] != Group[b]:
        if Children[Parent[Group[a]]] < Children[Parent[Group[b]]]:
            a = Parent[Group[a]]
        else:
            b = Parent[Group[b]]
    if Children[a] > Children[b]:
        return a
    else:
        return b
Parents = [Parent]
for i in range(30):
    X = [-1] * (N + 1)
    for i in range(N + 1):
        X[i] = Parents[-1][Parents[-1][i]]
    Parents.append(X)

def LCA_mae(x, y):
    while Height[x] > Height[y] + 1:
        for i in range(30):
            k = Parents[i][x]
            if k == -1 or k >= n or Height[k] <= Height[y]:
                x = Parents[i - 1][x]
                break
    return x
UP = [0] * (N + 1)
DOWN = [0] * (N + 1)
score = 0
for (x, y) in EDGE:
    if OK[x] == 1 and OK[y] == 1:
        if Parent[x] == y or Parent[y] == x:
            continue
        k = LCA(x, y)
        if k == x:
            DOWN[y] += 1
            k = LCA_mae(y, x)
            DOWN[k] -= 1
        elif k == y:
            DOWN[x] += 1
            k = LCA_mae(x, y)
            DOWN[k] -= 1
        else:
            score += 1
            DOWN[x] += 1
            DOWN[y] += 1
for x in TOP_SORT[1:]:
    DOWN[x] += DOWN[Parent[x]]
for x in TOP_SORT[1:][::-1]:
    UP[Parent[x]] += UP[x]
ANS = [0] * N
for i in range(N):
    if OK[i] == 1 and UP[i] + DOWN[i] == score:
        ANS[i] = 1
print(''.join(map(str, ANS[1:N])))

Solution (Python):
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
EDGE = [tuple(map(int, input().split())) for i in range(m)]
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
    while Group[x] != x:
        x = Group[x]
    return x

def Union(x, y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)
USE = [0] * m
for i in range(m):
    (x, y) = EDGE[i]
    if find(x) == find(y):
        USE[i] = 0
    else:
        USE[i] = 1
        Union(x, y)
E = [[] for i in range(n + 1)]
OK = [0] * (n + 1)
for i in range(m):
    if USE[i] == 1:
        (x, y) = EDGE[i]
        E[x].append(y)
        E[y].append(x)
        OK[x] = 1
        OK[y] = 1
N = n + 1
ROOT = 1
QUE = [ROOT]
Parent = [-1] * (N + 1)
Height = [-1] * (N + 1)
Parent[ROOT] = N
Height[ROOT] = 0
Child = [[] for i in range(N + 1)]
TOP_SORT = []
while QUE:
    x = QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to] == -1:
            Parent[to] = x
            Height[to] = Height[x] + 1
            Child[x].append(to)
            QUE.append(to)
Children = [1] * (N + 1)
for x in TOP_SORT[::-1]:
    Children[Parent[x]] += Children[x]
USE = [0] * N
Group = [i for i in range(N)]
for x in TOP_SORT:
    USE[x] = 1
    MAX_children = 0
    select_node = 0
    for to in E[x]:
        if USE[to] == 0 and Children[to] > MAX_children:
            select_node = to
            MAX_children = Children[to]
    for to in E[x]:
        if USE[to] == 0 and to == select_node:
            Group[to] = Group[x]

def LCA(a, b):
    while Group[a] != Group[b]:
        if Children[Parent[Group[a]]] < Children[Parent[Group[b]]]:
            a = Parent[Group[a]]
        else:
            b = Parent[Group[b]]
    if Children[a] > Children[b]:
        return a
    else:
        return b
Parents = [Parent]
for i in range(30):
    X = [-1] * (N + 1)
    for i in range(N + 1):
        X[i] = Parents[-1][Parents[-1][i]]
    Parents.append(X)

def LCA_mae(x, y):
    while Height[x] > Height[y] + 1:
        for i in range(30):
            k = Parents[i][x]
            if k == -1 or k >= n or Height[k] <= Height[y]:
                x = Parents[i - 1][x]
                break
    return x
DOWN = [0] * (N + 1)
score = 0
for (x, y) in EDGE:
    if OK[x] == 1 and OK[y] == 1:
        if Parent[x] == y or Parent[y] == x:
            continue
        k = LCA(x, y)
        if k == x:
            DOWN[y] += 1
            k = LCA_mae(y, x)
            DOWN[k] -= 1
        elif k == y:
            DOWN[x] += 1
            k = LCA_mae(x, y)
            DOWN[k] -= 1
        else:
            score += 1
            DOWN[x] += 1
            DOWN[y] += 1
for x in TOP_SORT[1:]:
    DOWN[x] += DOWN[Parent[x]]
ANS = [0] * N
for i in range(N):
    if OK[i] == 1 and DOWN[i] == score:
        ANS[i] = 1
print(''.join(map(str, ANS[1:N])))