题目描述树是一种重要的数据结构。它可以是空树没有节点也可以是由一个或多个节点以及连接它们的有向边组成的集合并满足以下性质存在唯一一个节点称为根没有指向它的有向边。除根节点外每个节点恰好有一条指向它的有向边。从根到每个节点存在唯一的一条有向路径。本题给出若干组有向边的描述要求判断每组边构成的图是否满足树的定义。输入格式输入包含若干测试用例每个测试用例由若干条边描述组成每条边描述为两个整数uuu和vvv表示从节点uuu到节点vvv有一条有向边。每个测试用例以一对000结束。所有节点编号均为正整数。整个输入以一对负数如−1-1−1-1结束。输出格式对于每个测试用例输出一行Case k is a tree.如果该组边构成一棵树。Case k is not a tree.否则。其中kkk为测试用例编号从111开始。样例输入6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1输出Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.题目分析判断一个有向图是否为一棵树需要验证以下条件对于非空树无环图中不能存在有向环。连通性从根节点出发能到达所有节点。入度条件根节点的入度为000其余节点的入度均为111。等价地一个有nnn个节点n0n0n0的有向图是树当且仅当没有重复边和自环。恰好有一个节点的入度为000。其他节点的入度均为111。图是弱连通的因为从根可到所有节点自然弱连通。本题中的空图没有任何边视为一棵树空树。解题思路数据结构使用mapint, setint存储邻接表方便检测重复边。使用mapint, int统计每个节点的入度。使用setint记录所有出现过的节点。读入与预处理对于每一条边u→vu \to vu→v若出现重复边即edges[u]中已包含vvv或自环uvu vuv则标记isTree false但继续读入其余边。将vvv的入度加111。将uuu和vvv加入节点集合。判断流程若边集合为空即没有读取到任何边则该图为空树直接判定为树。否则找到入度为000的节点作为根。若有多个或没有则不是树。从根开始进行广度优先搜索或深度优先搜索遍历所有可达节点若遇到已经访问过的节点则存在环不是树。遍历结束后若访问到的节点数不等于总节点数则图不连通不是树。若以上检查均通过则是树。注意入度条件在找根和 BFS 过程中已被隐式检查。若某个非根节点入度111则在BFS\texttt{BFS}BFS中该节点会被多次入队第二次访问时会被检测为环因此会判定为非树。若某个节点入度为000且不是根则它无法从根到达导致不连通也会判定为非树。复杂度分析设边数为mmm节点数为nnn。读入过程O(m)O(m)O(m)。查找根O(n)O(n)O(n)。广度优先搜索O(nm)O(n m)O(nm)。总体时间复杂度O(nm)O(n m)O(nm)空间复杂度O(nm)O(n m)O(nm)。代码实现// Is It A Tree// UVa ID: 615// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intfrom,to,cases0;while(cinfromto){if(from0)break;boolisTreetrue;mapint,setintedges;mapint,intdegrees;setintnodes;while(from0){if(edges[from].find(to)!edges[from].end()||fromto)isTreefalse;edges[from].insert(to);degrees[to];nodes.insert(from),nodes.insert(to);cinfromto;}if(edges.size()0)isTreetrue;else{intstart;for(autonode:nodes)if(degrees.find(node)degrees.end()){startnode;break;}setintvisited;queueintunvisited;unvisited.push(start);while(!unvisited.empty()){intcurrentunvisited.front();if(visited.find(current)!visited.end()){isTreefalse;break;}elsevisited.insert(current);unvisited.pop();for(autoedge:edges[current])unvisited.push(edge);}if(visited.size()!nodes.size())isTreefalse;}if(isTree)coutCase cases is a tree.\n;elsecoutCase cases is not a tree.\n;}return0;}总结本题通过检验入度、连通性和无环性来判断有向图是否为树。核心思想是统计入度找出唯一的根入度为000。从根开始遍历检查是否有环以及是否所有节点均可达。注意空树也是树。该解法简单高效适用于节点编号不连续且范围未知的情况利用map\texttt{map}map和set\texttt{set}set动态管理数据。