Jack Straws游戏：路径连接判断

"题目1127 Jack Straws 是一个计算机科学中的算法问题，属于ACM（算法竞赛）范畴。该题目涉及图论中的连通性判断。在一个名为Jack Straws的游戏场景中，玩家需要处理一系列的塑料或木制“吸管”（straws），它们被随意地放在桌面上。游戏的关键是判断给出的一些吸管是否可以通过一系列接触相连。具体来说，每组输入包含一个非零整数n表示吸管的数量，然后是若干对吸管的端点坐标，每一对代表一根吸管的起点和终点。输入数据保证没有非法输入，且不存在长度为零的吸管。 问题的核心是设计一个算法来确定两个特定吸管是否可以通过现有的其他吸管构成路径相连接。这里的连接规则不仅限于直接接触，还包括通过间接路径的连接。例如，如果A吸管与B吸管不直接相连，但A通过C吸管间接与D吸管相连，同时D吸管又与B吸管直接相连，则可以认为A和B是间接相连的。 输入部分由多组测试用例组成，每一组的第一行为一个整数n，表示当前吸管组的数量。接下来的n行每行包含两个整数，分别代表吸管的起始和结束点。最后会有一个特殊的测试用例，其中a=0=b，表示输入结束。 输出要求对于每一对吸管，如果它们是连通的，输出"CONNECTED"，反之则是"NOTCONNECTED"。这里需要注意的是，每个吸管被视为自身连通。 解决这个问题的一种常见方法是使用图的表示和遍历技巧。首先，将输入的端点坐标转换为图中的节点，然后构建一个邻接表或邻接矩阵来表示吸管之间的连接关系。接下来，使用深度优先搜索（DFS）或广度优先搜索（BFS）等算法来检查两个指定节点是否在同一个连通分量中。如果存在路径，则返回"CONNECTED"，否则返回"NOTCONNECTED"。 总结来说，这道题目考察了选手对数据结构、图算法特别是连通性分析的理解和实现能力，需要能够高效地处理大规模数据，并正确识别和利用吸管间的相互联系。"