Problem p02536 (python)

Fixed submission:
# There are N cities numbered 1 through N, and M bidirectional roads numbered 1
# through M. Road i connects City A_i and City B_i.
# 
# Snuke can perform the following operation zero or more times:
# 
#  * Choose two distinct cities that are not directly connected by a road, and
#    build a new road between the two cities.
# 
# After he finishes the operations, it must be possible to travel from any city to
# any other cities by following roads (possibly multiple times).
# 
# What is the minimum number of roads he must build to achieve the goal?

# Solution:
#   Use UnionFind to start with groups 1..N and merge as directed by the roads data.
#   If there are G distinct groups after all the merges, then G-1 roads are required
#   to provide the necessary linkages.

class UnionFind:
    # The nodes will be numbered 1..n.
    def __init__(s, n):
        s.n_ = n
        s.ngroups_ = n
        s.parent_  = [i for i in range(n+1)]
          # index zero is ignored

    # Number of nodes.
    def n(s):
        return s.n_

    # Number of distict groups.
    def ngroups(s):
        return s.ngroups_

    # Returns the ultimate parent node of node i, and resets the parent so the chain is
    # shorter for future queries.
    def find(s, i):
        x = i
        while True:
            y = s.parent_[x]
            if x == y:
                # We've found the root of the group.
                s.parent_[i] = x
                return x
            else:
                x = y

    # -> True/False
    def same_group(s, i, j):
        return s.find(i) == s.find(j)

    # Generator of (node_id, group_id) for all nodes.
    def items(s):
        return ((i, s.find(i)) for i in range(1, s.n_ + 1))

    # Merges two groups. Returns True if a merge actually took place, or False if they
    # were in the same group anyway.
    def union(s, i, j):
        x, y = s.find(i), s.find(j)
        if x == y:
            # Same group already.
            return False
        else:
            s.parent_[x] = y
            s.parent_[i] = y
            s.ngroups_ -= 1
            return True

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]

U = UnionFind(N)

# Process each road and merge groups accordingly.
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    U.union(a, b)

# Get and print the answer.
answer = U.ngroups() - 1
print(answer)

Buggy submission (verdict: Runtime Error):
# There are N cities numbered 1 through N, and M bidirectional roads numbered 1
# through M. Road i connects City A_i and City B_i.
# 
# Snuke can perform the following operation zero or more times:
# 
#  * Choose two distinct cities that are not directly connected by a road, and
#    build a new road between the two cities.
# 
# After he finishes the operations, it must be possible to travel from any city to
# any other cities by following roads (possibly multiple times).
# 
# What is the minimum number of roads he must build to achieve the goal?

# Solution:
#   Each road either: creates a new group; extends an existing one; or merges two
#     existing groups.
#   Use array GROUP to track the group of each city, all set to None initially.
#   Each group has a PARENT. A new group is created when two groups are merged, and
#     each group points to the new one as its parent. The new group has no parent (None).
#   After processing all roads: count the unique groups (i.e. groups with no parent) and
#     the cities with no group (i.e. they have no road).
#   If there are 6 unique groups, then 5 roads will ensure they are all connected.
#   If there are 4 Nones, then 4 roads are needed to connect them to groups.
#   Answer = (#groups - 1) + #Nones

def count(gen):
    n = 0
    for x in gen:
        if x:
            n += 1
    return n

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]
# Initialize GROUP and PARENT.
GROUP = [None for _ in range(N+1)]
PARENT = dict()
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    #print(f"road: {a} {b}")
    if GROUP[a] and GROUP[b]:
        # We have a merger.
        assert GROUP[a] != GROUP[b]
        G += 1
        ##print(f"  merger - groups {GROUP[a]} and {GROUP[b]} --> {G}")
        PARENT[G] = None
        PARENT[GROUP[a]] = G
        PARENT[GROUP[b]] = G
        GROUP[a] = G
        GROUP[b] = G
    elif GROUP[a]:
        # Extend existing group.
        GROUP[b] = GROUP[a]
        ##print(f"  extend group {GROUP[a]}")
    elif GROUP[b]:
        # Extend existing group.
        GROUP[a] = GROUP[b]
        ##print(f"  extend group {GROUP[b]}")
    else:
        # Neither has a group; we start a new one.
        G += 1
        ##print(f"  new group {G}")
        PARENT[G] = None
        GROUP[a] = G
        GROUP[b] = G

##print()
##print(GROUP)
##print(PARENT)

# Count the unique groups and the isolated cities.
num_groups   = count(PARENT[x] is None for x in range(1, G+1))
num_isolated = count(GROUP[x]  is None for x in range(1, N+1))

##print(num_groups, num_isolated)

# Get the answer.
answer = (num_groups - 1) + num_isolated

print(answer)

Buggy submission (verdict: Runtime Error):
# There are N cities numbered 1 through N, and M bidirectional roads numbered 1
# through M. Road i connects City A_i and City B_i.
# 
# Snuke can perform the following operation zero or more times:
# 
#  * Choose two distinct cities that are not directly connected by a road, and
#    build a new road between the two cities.
# 
# After he finishes the operations, it must be possible to travel from any city to
# any other cities by following roads (possibly multiple times).
# 
# What is the minimum number of roads he must build to achieve the goal?

# Solution:
#   The road data needs to be completely sorted so we don't get two disparate groups
#   suddenly being joined.
#   Each road either creates a new group or extends an existing one.
#   Use array GROUP for this purpose, all initialized to None.
#   After processing all roads, do a linear scan to count the Nones. We will already
#   know how many groups there are.
#   If there are 6 groups, then 5 roads will ensure they are all connected.
#   If there are 4 Nones, then 4 roads are needed to connect them to groups.
#   Answer = (#groups - 1) + #Nones

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]
# Read A (details of roads) and sort the list.
A = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    A.append((a,b))
A.sort()
# Initialise GROUP (the group to which each ciy belongs). We use indices 1..N.
GROUP = [None for _ in range(N+1)]
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for a,b in A:
    #print((a,b), GROUP[1:])
    if GROUP[a] and GROUP[b]:
        # I believe this should not logically happen.
        print("Logical error")
        exit(1)
    elif GROUP[a]:
        GROUP[b] = GROUP[a]
    elif GROUP[b]:
        GROUP[a] = GROUP[b]
    else:
        # Neither has a group; we start a new one.
        G += 1
        GROUP[a] = G
        GROUP[b] = G

# Linear scan to count what we have. Ignore index 1.
num_nones = 0
for i in range(1,N+1):
    if GROUP[i] == None:
        num_nones += 1

# Get the answer.
answer = (G-1) + num_nones

print(answer)

Buggy submission (verdict: Runtime Error):
# There are N cities numbered 1 through N, and M bidirectional roads numbered 1
# through M. Road i connects City A_i and City B_i.
# 
# Snuke can perform the following operation zero or more times:
# 
#  * Choose two distinct cities that are not directly connected by a road, and
#    build a new road between the two cities.
# 
# After he finishes the operations, it must be possible to travel from any city to
# any other cities by following roads (possibly multiple times).
# 
# What is the minimum number of roads he must build to achieve the goal?

# Solution:
#   The road data needs to be completely sorted so we don't get two disparate groups
#   suddenly being joined.
#   Each road either creates a new group or extends an existing one.
#   Use array GROUP for this purpose, all initialized to None.
#   After processing all roads, do a linear scan to count the Nones. We will already
#   know how many groups there are.
#   If there are 6 groups, then 5 roads will ensure they are all connected.
#   If there are 4 Nones, then 4 roads are needed to connect them to groups.
#   Answer = (#groups - 1) + #Nones

import sys
IN = sys.stdin

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in IN.readline().split()]
# Read A (details of roads) and sort each pair and then the whole list.
A = []
for line in IN.readlines():
    a, b = line.split()
    a, b = int(a), int(b)
    a, b = sorted([a,b])
    A.append((a,b))
A.sort()
# Initialise G (the group to which each ciy belongs). We use indices 1..N.
GROUP = [None for _ in range(N+1)]
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for a,b in A:
    if GROUP[a] and GROUP[b]:
        # I believe this should not logically happen.
        print("Logical error")
        exit(1)
    elif GROUP[a]:
        GROUP[b] = GROUP[a]
    elif GROUP[b]:
        GROUP[a] = GROUP[b]
    else:
        # Neither has a group; we start a new one.
        G += 1
        GROUP[a] = G
        GROUP[b] = G

# Linear scan to count what we have. Ignore index 1.
num_nones = 0
for i in range(1,N+1):
    if GROUP[i] == None:
        num_nones += 1

# Get the answer.
answer = (G-1) + num_nones

print(answer)