Overview

Given \(N\) players, we perform \(M\) team merge + flag color assignment operations, then find the number of distinct colors among teams that have a flag color assigned. We use Union-Find (disjoint set data structure) to efficiently manage team merges.

Analysis

Key Observations

1. Team merging can be efficiently handled with Union-Find (Union by Rank + Path Compression).
2. Each operation “merges the teams of two players and assigns a color to the merged team.” Since colors are overwritten, if a color is assigned to the same team multiple times, only the last assigned color remains.
3. What we ultimately need is the number of distinct colors among “teams that have a flag color assigned.” Teams that were never involved in any operation are ignored.

Problems with a Naive Approach

If team merging is managed by copying lists, it takes \(O(N)\) time in the worst case, resulting in \(O(NM)\) overall, which risks TLE. Using Union-Find, each operation can be processed in nearly \(O(1)\) (precisely, the inverse Ackermann function).

Color Management

In Union-Find, the root (representative) of each team is uniquely determined. If we always record the color at the root, it can be correctly managed even after merges. We implement union(a, b) so that it returns the new root, and assign color \(C_i\) to that root.

Algorithm

1. Initialization: Prepare a Union-Find where each player \(i\) is their own parent. Initialize the color array color[i] to None (unset).

2. Process the \(M\) operations in order:

   • Merge the teams of players \(U_i\) and \(V_i\) using union.
   • union returns the root (representative) after merging.
   • Assign color \(C_i\) to that root (overwriting any previous color).

3. Final aggregation:

   • For all players \(1\) through \(N\), find the root using find(i) and enumerate all team roots without duplicates.
   • For teams whose root has a color assigned (color[root] is not None), add the color to a set.
   • The size of the set is the answer.

Concrete Example

For \(N=4, M=2\) with operations \((1,2,\text{red}), (3,4,\text{red})\): - Operation 1: Players 1 and 2 merge → Team {1,2} gets color “red” - Operation 2: Players 3 and 4 merge → Team {3,4} gets color “red” - Ultimately, there are 2 teams with colors assigned, but both are “red,” so the answer is 1.

Complexity

• Time complexity: \(O((N + M) \cdot \alpha(N))\)
  • \(\alpha(N)\) is the inverse Ackermann function, which is effectively constant. Each Union-Find operation (find, union) runs in nearly \(O(1)\).
  • The final aggregation scans all players in \(O(N)\).
• Space complexity: \(O(N)\)
  • The Union-Find parent array, rank array, and color array each use \(O(N)\).

Implementation Notes

• Return value of union: By implementing it to return the root after merging, we can assign the color to the correct root. This requires only a small modification to a standard Union-Find.

• Path Compression: Within find, setting parent[x] = parent[parent[x]] keeps the tree height low for faster performance.

• Deduplication during final aggregation: A set called seen_roots is used to avoid counting the same root multiple times.

• Color overwriting: When the same team is involved in multiple operations, the color gets overwritten, but since we always record the color at the root, the last assigned value naturally remains.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    
    parent = list(range(N + 1))
    rank = [0] * (N + 1)
    color = [None] * (N + 1)  # color of the team represented by root
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return ra
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1
        return ra
    
    for _ in range(M):
        u, v, c = map(int, input().split())
        root = union(u, v)
        color[root] = c
    
    # Collect colors of all teams that have a color set
    seen_roots = set()
    colors = set()
    for i in range(1, N + 1):
        r = find(i)
        if r not in seen_roots:
            seen_roots.add(r)
            if color[r] is not None:
                colors.add(color[r])
    
    print(len(colors))

main()

This editorial was generated by claude4.6opus-thinking.