Overview

After processing a large number of “team mergers” and “color overwrites for merged teams,” the problem asks you to count the number of distinct flag colors among all teams that exist at the end.
Union-Find (DSU) is the optimal choice for team management.

Analysis

The essence of this problem is efficiently managing which connected component (team) each player belongs to, rather than tracking individual player affiliations.
For each operation:

1. Merge the teams that \(U_i\) and \(V_i\) belong to (do nothing if they’re already in the same team)
2. Overwrite that team’s color with \(C_i\)

Key Observations

• Each operation “connects two vertices,” so teams can be treated as connected components.
• Union-Find is the standard tool for managing connected components.
• Only one color needs to be stored per team (there’s no need to store it per member).

Why a Naive Solution Is Too Slow

For example, if you were to: - Scan all players each time to reconstruct teams - Merge the member lists of two teams

Such an implementation would approach \(O(NM)\) in the worst case, which is too slow for \(N=2\times10^5,\ M=1.5\times10^5\).

How to Solve It

Use Union-Find to manage the following:

• parent[x]: parent of node x
• size[x]: size of the set rooted at x (for union by size)
• color[x]: current color of the team represented by root x (0 means unset)

For each operation \((u,v,c)\), find the roots ru, rv, then:

• If ru != rv, merge the smaller set into the larger set, and set the new root’s color to c
• If ru == rv, overwrite that root’s color with c

Finally, look at only “nodes that are roots and whose color is not unset,” insert their colors into a set, and the size of the set gives the number of distinct colors.

Algorithm

1. Initialization
   
   • Each player is a set with itself as the root
     
   • All color values are 0 (unset)
2. Process each operation \((u,v,c)\)
   
   1. ru = find(u), rv = find(v)
   2. If ru != rv:
      
      • Make the one with larger size the new root (union by size)
      • Link the parent
      • Update the size
      • Set the new root’s color to c
   3. If ru == rv:
      
      • Set that root’s color to c
3. For all elements i=1..N:
   
   • If parent[i] == i (it’s a root) and color[i] != 0, add it to seen
4. Output len(seen)

Complexity

• Time complexity: \(O((N+M)\alpha(N))\) (nearly linear)
• Space complexity: \(O(N)\)

Implementation Notes

• Implement find with path compression for speedup.

• Use union by size during merges to keep the tree height small.

• Colors are “only meaningful at roots,” so during the final aggregation, only roots need to be checked.

• Since 0 is used to indicate an unset color, this does not conflict with the constraint that input colors \(C_i\) are positive integers.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())

    parent = list(range(N + 1))
    size = [1] * (N + 1)
    color = [0] * (N + 1)  # 0 means unset

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

    for _ in range(M):
        u, v, c = map(int, input().split())
        ru = find(u)
        rv = find(v)

        if ru != rv:
            if size[ru] < size[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            size[ru] += size[rv]
            color[ru] = c
        else:
            color[ru] = c

    seen = set()
    for i in range(1, N + 1):
        if parent[i] == i and color[i] != 0:
            seen.add(color[i])

    print(len(seen))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.