【杭电ACM1271】“杭电ACM1271”是杭州电子科技大学（简称杭电）在ACM-ICPC竞赛中的一道经典题目，编号为1271。该题主要考察选手对图论算法的理解与应用能力，尤其是关于图的遍历和连通性判断的相关知识。
本题的核心在于判断一个无向图是否是一个“树”结构。树是一种特殊的图，它具有以下特点：
- 有且仅有一个连通分量；
- 没有环；
- 边数等于顶点数减一。
因此，解题的关键在于如何正确地判断输入的图是否符合这些条件。
题目描述简要
题目给出若干个测试用例，每个用例包含若干条边，要求判断这些边是否构成一棵树。
输入格式大致如下：
- 每组测试数据的第一行是一个整数n，表示顶点的数量。
- 接下来是n-1条边的信息，每条边由两个整数u和v组成，表示顶点u和顶点v之间有一条边。
输出应为“YES”或“NO”，分别表示该图是否是一棵树。
解题思路
为了判断是否为树，可以采用以下步骤：
1. 统计顶点数和边数：如果边数不等于顶点数减一，则直接返回“NO”。
2. 使用并查集（Union-Find）或DFS/BFS进行连通性检查：确保所有顶点属于同一个连通分量。
3. 检查是否有环：如果存在环，则不是树。
示例表格
| 测试用例 | 顶点数 n | 边数 m | 是否为树 | 判断依据 |
| 1 | 4 | 3 | YES | 边数 = n - 1，且连通无环 |
| 2 | 5 | 5 | NO | 边数 ≠ n - 1 |
| 3 | 3 | 2 | YES | 边数 = n - 1，且连通无环 |
| 4 | 6 | 5 | NO | 存在环 |
| 5 | 2 | 1 | YES | 边数 = n - 1，连通无环 |
总结
杭电ACM1271是一道典型的图论问题，考查了选手对树结构的理解和实现能力。通过合理的数据结构（如并查集）和算法（如DFS/BFS），可以高效地判断输入是否构成一棵树。此题不仅锻炼了逻辑思维，也提升了对图结构的处理能力，是ACM竞赛中较为基础但重要的题目之一。
