题解：合法的景点划分问题

问题分析

我们需要将所有景点划分为三个集合 ( A )、( B )、( C )（规模分别为 ( a )、( b )、( c )），使得至少两个集合是连通的（集合的导出子图连通）。若存在这样的划分则输出一种，否则输出全0。

解题思路

核心是利用图的连通块性质和集合规模约束，通过分析连通块的大小来构造合法划分。

关键观察

• 一个集合连通的充要条件是其导出子图连通。
• 我们可以通过分析图中连通块的大小，尝试构造满足 ( a, b, c ) 规模且至少两个集合连通的划分。

具体策略

策略1：单个连通块满足集合规模

若存在一个连通块的大小恰好等于 ( a )（或 ( b )、( c )），则可将该连通块作为集合 ( A )（或 ( B )、( C )），剩余景点尝试划分为另外两个集合（规模分别为 ( b ) 和 ( c )）。

策略2：两个连通块满足规模之和

若存在两个连通块的大小之和恰好等于 ( a+b )（或 ( a+c )、( b+c )），则可将这两个连通块分别作为集合 ( A ) 和 ( B )（或 ( A ) 和 ( C )、( B ) 和 ( C )），剩余景点作为第三个集合。

步骤详解

1. 计算所有连通块：通过BFS或DFS遍历图，记录每个连通块的节点集合和大小。
2. 尝试策略1：检查是否存在连通块大小等于 ( a )、( b ) 或 ( c )。若存在，将其作为一个集合，剩余节点分配到另外两个集合，验证规模是否满足。
3. 尝试策略2：检查是否存在两个连通块大小之和等于 ( a+b )、( a+c ) 或 ( b+c )。若存在，将其作为两个集合，剩余节点作为第三个集合。
4. 验证连通性：若构造的划分中至少两个集合的导出子图连通，则为合法解；否则继续尝试其他情况。若所有情况都不满足，输出全0。

复杂度分析

• 连通块计算的时间复杂度为 ( O(n + m) )（( n ) 是景点数，( m ) 是道路数），这是因为BFS/DFS遍历每个节点和边各一次。
• 后续的连通块大小检查为线性时间，因此整体复杂度为 ( O(n + m) )，可处理题目给定的数据范围。

总结

该问题的核心是利用图的连通块性质，通过分析连通块的大小来构造满足规模和连通性要求的划分。通过“单个连通块”和“两个连通块之和”两种策略，可以高效地解决问题。