C++ / 设备分组连通 算法挑战

设备分组连通

在没有分步提示的新场景中，独立应用本单元的数据结构。

需求与输入输出

第一行 n q，初始每个设备独立。LINK u v 合并两设备所在组；ASK u v 查询是否同组，同组 YES，否则 NO。设备编号 1～n。

使用 C++17。输入符合协议，编号从 1 开始；除特别说明外，n、q 均不超过 100000。不要输出额外提示语。

样例输入

3 4
ASK 1 2
LINK 1 2
LINK 2 3
ASK 1 3

样例输出

NO
YES

验收要求

• 正确处理单元素、空结构或无匹配情况。
• 更新后查询反映最新状态；多个测试之间不共享状态。
• 累计量使用 long long。

实现建议

查找代表节点，再合并集合；重复合并不应破坏结构，加入路径压缩避免长链。

先手工推演样例，再独立编写实现。通过测试后需正式提交，才计入编程成果。