Edges in MST (Codeforces 160D)
Tags: Others, dsu

You are given a connected weighted undirected graph without any loops and multiple edges. Let us remind you that a graph's spanning tree is defined as an acyclic connected subgraph of the given graph that includes all of the graph's vertexes. The weight of a tree is defined as the sum of weights of the edges that the given tree contains. The minimum spanning tree (MST) of a graph is defined as the graph's spanning tree having the minimum possible weight. For any connected graph obviously exists the minimum spanning tree, but in the general case, a graph's minimum spanning tree is not unique.Your task is to determine the following for each edge of the given graph: whether it is either included in any MST, or included at least in one MST, or not included in any MST.

Input: The first line contains two integers n and m (2 ≤ n ≤ 105, ) — the number of the graph's vertexes and edges, correspondingly. Then follow m lines, each of them contains three integers — the description of the graph's edges as "ai bi wi" (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106, ai ≠ bi), where ai and bi are the numbers of vertexes connected by the i-th edge, wi is the edge's weight. It is guaranteed that the graph is connected and doesn't contain loops or multiple edges.

Output: Print m lines — the answers for all edges. If the i-th edge is included in any MST, print "any"; if the i-th edge is included at least in one MST, print "at least one"; if the i-th edge isn't included in any MST, print "none". Print the answers for the edges in the order in which the edges are specified in the input.

Note: In the second sample the MST is unique for the given graph: it contains two first edges.In the third sample any two edges form the MST for the given graph. That means that each edge is included at least in one MST.

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

3 3
1 2 1
2 3 1
1 3 2

3 3
1 2 1
2 3 1
1 3 1

Sample Outputs:
none
any
at least one
at least one
any

any
any
none

at least one
at least one
at least one

Solution (Python):
import sys, threading
from collections import defaultdict
(n_nodes, n_edges) = map(int, input().split())
edges = list()
results = defaultdict(lambda : 'any')
highest = defaultdict(lambda : -1)
to_check = defaultdict(list)
graph = defaultdict(list)

class UDFS:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for i in range(n)]

    def __str__(self):
        """"""
        return '\n'.join((f'{e} -> {i}' for (i, e) in enumerate(self.parents)))

    def get_group(self, a):
        if a == self.parents[a]:
            return a
        self.parents[a] = self.get_group(self.parents[a])
        return self.parents[a]

    def is_parent(self, n):
        return n == self.get_group(n)

    def is_same_group(self, a, b):
        return self.get_group(a) == self.get_group(b)

    def join(self, a, b):
        parent_a = self.get_group(a)
        parent_b = self.get_group(b)
        if self.ranks[parent_a] > self.ranks[parent_b]:
            self.parents[parent_b] = parent_a
        else:
            self.parents[parent_a] = parent_b
            self.ranks[parent_b] += int(self.ranks[parent_a] == self.ranks[parent_b])

    def count(self):
        """"""
        count = 0
        for n in range(self.n):
            count += self.is_parent(n)
        return count

def dfs(a, depth, p):
    global edges
    global results
    global highest
    global graph
    if highest[a] != -1:
        return highest[a]
    minimum = depth
    highest[a] = depth
    for (w, a, b, i) in graph[a]:
        if i == p:
            continue
        nextt = dfs(b, depth + 1, i)
        if nextt <= depth:
            results[i] = 'at least one'
        else:
            results[i] = 'any'
        minimum = min(minimum, nextt)
        highest[a] = minimum
    return highest[a]

def main():
    global edges
    global results
    global highest
    global graph
    for i in range(n_edges):
        (a, b, w) = map(int, input().split())
        edges.append((w, a - 1, b - 1, i))
    edges = sorted(edges, key=lambda x: x[0])
    dsu = UDFS(n_nodes)
    i = 0
    while i < n_edges:
        counter = 0
        j = i
        while j < n_edges and edges[j][0] == edges[i][0]:
            if dsu.get_group(edges[j][1]) == dsu.get_group(edges[j][2]):
                results[edges[j][3]] = 'none'
            else:
                to_check[counter] = edges[j]
                counter += 1
            j += 1
        for k in range(counter):
            (w, a, b, i) = to_check[k]
            ra = dsu.get_group(a)
            rb = dsu.get_group(b)
            graph[ra].append((w, ra, rb, i))
            graph[rb].append((w, rb, ra, i))
        for k in range(counter):
            dfs(to_check[k][1], 0, -1)
        for k in range(counter):
            (w, a, b, i) = to_check[k]
            ra = dsu.get_group(a)
            rb = dsu.get_group(b)
            dsu.join(ra, rb)
            graph[ra] = list()
            graph[rb] = list()
            highest[ra] = -1
            highest[rb] = -1
        counter = 0
        i = j
    for i in range(n_edges):
        print(results[i])
if __name__ == '__main__':
    sys.setrecursionlimit(2 ** 32 // 2 - 1)
    threading.stack_size(1 << 27)
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()

Solution (Python):
import sys, threading
from heapq import heappop, heappush
from collections import defaultdict
(n_nodes, n_edges) = map(int, input().split())
edges = list()
results = defaultdict(lambda : 'any')
highest = defaultdict(lambda : -1)
to_check = defaultdict(list)
graph = defaultdict(list)

class UDFS:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for i in range(n)]

    def __str__(self):
        """"""
        return '\n'.join((f'{e} -> {i}' for (i, e) in enumerate(self.parents)))

    def get_group(self, a):
        if a == self.parents[a]:
            return a
        self.parents[a] = self.get_group(self.parents[a])
        return self.parents[a]

    def is_parent(self, n):
        return n == self.get_group(n)

    def is_same_group(self, a, b):
        return self.get_group(a) == self.get_group(b)

    def join(self, a, b):
        parent_a = self.get_group(a)
        parent_b = self.get_group(b)
        if self.ranks[parent_a] > self.ranks[parent_b]:
            self.parents[parent_b] = parent_a
        else:
            self.parents[parent_a] = parent_b
            self.ranks[parent_b] += int(self.ranks[parent_a] == self.ranks[parent_b])

    def count(self):
        """"""
        count = 0
        for n in range(self.n):
            count += self.is_parent(n)
        return count

def dfs(a, depth, p):
    global edges
    global results
    global highest
    global graph
    if highest[a] != -1:
        return highest[a]
    minimum = depth
    highest[a] = depth
    for (w, a, b, i) in graph[a]:
        if i == p:
            continue
        nextt = dfs(b, depth + 1, i)
        if nextt <= depth:
            results[i] = 'at least one'
        else:
            results[i] = 'any'
        minimum = min(minimum, nextt)
        highest[a] = minimum
    return highest[a]

def main():
    global edges
    global results
    global highest
    global graph
    for i in range(n_edges):
        (a, b, w) = map(int, input().split())
        edges.append((w, a - 1, b - 1, i))
    edges = sorted(edges, key=lambda x: x[0])
    dsu = UDFS(n_nodes)
    i = 0
    while i < n_edges:
        counter = 0
        j = i
        while j < n_edges and edges[j][0] == edges[i][0]:
            if dsu.get_group(edges[j][1]) == dsu.get_group(edges[j][2]):
                results[edges[j][3]] = 'none'
            else:
                to_check[counter] = edges[j]
                counter += 1
            j += 1
        for k in range(counter):
            (w, a, b, i) = to_check[k]
            ra = dsu.get_group(a)
            rb = dsu.get_group(b)
            graph[ra].append((w, ra, rb, i))
            graph[rb].append((w, rb, ra, i))
        for k in range(counter):
            dfs(to_check[k][1], 0, -1)
        for k in range(counter):
            (w, a, b, i) = to_check[k]
            ra = dsu.get_group(a)
            rb = dsu.get_group(b)
            dsu.join(ra, rb)
            graph[ra] = list()
            graph[rb] = list()
            highest[ra] = -1
            highest[rb] = -1
        counter = 0
        i = j
    for i in range(n_edges):
        print(results[i])
if __name__ == '__main__':
    sys.setrecursionlimit(2 ** 32 // 2 - 1)
    threading.stack_size(1 << 27)
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()

Solution (Python):
import sys, threading
from heapq import heappop, heappush
from collections import defaultdict
(n_nodes, n_edges) = map(int, input().split())
edges = list()
results = defaultdict(lambda : 'any')
highest = defaultdict(lambda : -1)
to_check = defaultdict(list)
graph = defaultdict(list)

class UDFS:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for i in range(n)]

    def __str__(self):
        """"""
        return '\n'.join((f'{e} -> {i}' for (i, e) in enumerate(self.parents)))

    def get_group(self, a):
        if a == self.parents[a]:
            return a
        self.parents[a] = self.get_group(self.parents[a])
        return self.parents[a]

    def is_parent(self, n):
        return n == self.get_group(n)

    def is_same_group(self, a, b):
        return self.get_group(a) == self.get_group(b)

    def join(self, a, b):
        parent_a = self.get_group(a)
        parent_b = self.get_group(b)
        if self.ranks[parent_a] > self.ranks[parent_b]:
            self.parents[parent_b] = parent_a
        else:
            self.parents[parent_a] = parent_b
            self.ranks[parent_b] += int(self.ranks[parent_a] == self.ranks[parent_b])

    def count(self):
        """"""
        count = 0
        for n in range(self.n):
            count += self.is_parent(n)
        return count

def dfs(a, depth, p):
    global edges
    global results
    global highest
    global graph
    if highest[a] != -1:
        return highest[a]
    minimum = depth
    highest[a] = depth
    for (w, a, b, i) in graph[a]:
        if i == p:
            continue
        nextt = dfs(b, depth + 1, i)
        if nextt <= depth:
            results[i] = 'at least one'
        else:
            results[i] = 'any'
        minimum = min(minimum, nextt)
        highest[a] = minimum
    return highest[a]

def main():
    global edges
    global results
    global highest
    global graph
    for i in range(n_edges):
        (a, b, w) = map(int, input().split())
        edges.append((w, a - 1, b - 1, i))
    edges = sorted(edges, key=lambda x: x[0])
    dsu = UDFS(n_nodes)
    i = 0
    while i < n_edges:
        counter = 0
        j = i
        while j < n_edges and edges[j][0] == edges[i][0]:
            if dsu.get_group(edges[j][1]) == dsu.get_group(edges[j][2]):
                results[edges[j][3]] = 'none'
            else:
                to_check[counter] = edges[j]
                counter += 1
            j += 1
        for k in range(counter):
            (w, a, b, i) = to_check[k]
            ra = dsu.get_group(a)
            rb = dsu.get_group(b)
            graph[ra].append((w, ra, rb, i))
            graph[rb].append((w, rb, ra, i))
        for k in range(counter):
            dfs(to_check[k][1], 0, -1)
        for k in range(counter):
            (w, a, b, i) = to_check[k]
            ra = dsu.get_group(a)
            rb = dsu.get_group(b)
            dsu.join(ra, rb)
            graph[ra] = list()
            graph[rb] = list()
            highest[ra] = -1
            highest[rb] = -1
        counter = 0
        i = j
    for i in range(n_edges):
        print(results[i])
if __name__ == '__main__':
    sys.setrecursionlimit(2 ** 32 // 2 - 1)
    threading.stack_size(1 << 27)
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()