UVa _ 10336 _ Rank the Languages

 import sys

# Constants

MX = 10000

class Type:

    def __init__(self, id=None, value=0):

        self.id = id

        self.value = value

def comp(a):

    # Comparison function for sorting ranks

    # Primary sort: descending order of value (using negative to achieve descending)

    # Secondary sort: ascending order of id (in case of equal values)

    # Useful for ranking components by size and then by identifier

    return (-a.value, a.id)

def init(h, w):

    # Initialize a list of Type objects with default values

    # Creates an empty data structure of specified dimensions

    # Useful for pre-allocating space for graph-related data structures

    return [Type() for _ in range(h * w)]

def set_rank(ranks, c, r):

    for rank in ranks:

        if rank.id == c:

            rank.value += r

            return    

    new_rank = Type(id=c, value=r)

    ranks.append(new_rank)

def dfs_visit(graph, a, b, h, w):

    # Capturing the original color/type of the current cell before modification

    temp_c = graph[a][b]

    # label v as discovered

    # Mark the current cell as 'visited' to prevent re-exploration and avoid infinite recursion

    graph[a][b] = 'G'

    

    # Directional movements represent the possible traversal directions

    # These coordinates allow checking adjacent cells (left, up, right, down)

    dr = [0, -1, 0, 1]

    dc = [-1, 0, 1, 0]

    # for all directed edges from v to w that are in G.adjacentEdges(v) do

    # Iterate through all four possible adjacent directions

    for i in range(4):

        r = dr[i] + a

        c = dc[i] + b

        # if vertex w is not labeled as discovered then

        # Check if the adjacent cell is within graph boundaries and of the same color/type

        if (0 <= r < h and 0 <= c < w and 

            graph[r][c] == temp_c):

            # recursively call DFS(G, w)

            # Explore the connected component by recursively visiting adjacent cells

            dfs_visit(graph, r, c, h, w)

    # Mark the cell as completely explored to distinguish from undiscovered cells

    graph[a][b] = 'B'

def dfs(graph, h, w):

    # Initialize a list to store ranked components

    ranks = []

    # for all directed edges from v to w that are in G.adjacentEdges(v) do

    # Traverse through entire graph to find and explore connected components

    for i in range(h):

        for j in range(w): 

            # if vertex w is not labeled as discovered then

            # Check if the current cell hasn't been explored in previous DFS calls

            if graph[i][j] not in ['G', 'B']: 

                # Assign initial rank to the newly discovered component

                set_rank(ranks, graph[i][j], 1)  

                # recursively call DFS(G, w)

                # Start DFS from this undiscovered cell to explore its entire component

                dfs_visit(graph, i, j, h, w)

    return ranks

def process_world(h, w, graph_input):

    # Convert input to 2D list for easier manipulation

    graph = [list(row) for row in graph_input]

    # Perform depth-first search to identify and rank components

    ranks = dfs(graph, h, w)

    # Sort ranks in descending order of component size, with secondary sorting by component ID

    ranks.sort(key=comp)

    return ranks

test_cases = int(input())

cases = 0

for _ in range(test_cases):

    h, w = map(int, input().split())

    graph_input = [input() for _ in range(h)]

    cases += 1

    ranks = process_world(h, w, graph_input)

    print(f"World #{cases}")

    for rank in ranks:

        print(f"{rank.id}: {rank.value}")