题解

思路

把每种颜色看成一个顶点，每张卡片看成连接其两面颜色的一条边（两面同色时是自环）。

做法

不同连通块互不影响。对一个含 $V$ 个顶点、$E$ 条边的连通块，显然最多贡献 $\min(V,E)$ 种颜色；若它是树，则 $E=V-1$，选定根后让每条父子边露出子节点即可达到 $V-1$；若它含环，则取一棵生成树并用树边露出除根外的所有顶点，再用一条非树边露出根，可达到全部 $V$ 个顶点。因此每个连通块的最优值恰为 $\min(V,E)$。

复杂度

用并查集合并每条边的两个端点，再统计每个根对应的点数和边数并求和，时间复杂度为 $O(N\alpha(N))$，空间复杂度为 $O(C)$，其中 $C\le4\times10^5$。