NFLS 2024.9.14 T4

SkyMaths's Blogs / 2024-10-16 / 原文

给定一个大小为 \(R * C\) 的网格图和 \(m\) 个水平或竖直的隔断,问有多少个连通块 \((m <= 2e5)\)

做法1

考虑平面图欧拉定理 面数 = 边数 - 点数 + 边联通块个数 + 1

做法2

维护一个“并查集”