UVa 615 Is It A Tree

题目描述

树是一种重要的数据结构。它可以是空树（没有节点），也可以是由一个或多个节点以及连接它们的有向边组成的集合，并满足以下性质：

• 存在唯一一个节点，称为根，没有指向它的有向边。
• 除根节点外，每个节点恰好有一条指向它的有向边。
• 从根到每个节点存在唯一的一条有向路径。

本题给出若干组有向边的描述，要求判断每组边构成的图是否满足树的定义。

输入格式

输入包含若干测试用例，每个测试用例由若干条边描述组成，每条边描述为两个整数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.

题目分析

判断一个有向图是否为一棵树，需要验证以下条件（对于非空树）：

1. 无环：图中不能存在有向环。
2. 连通性：从根节点出发能到达所有节点。
3. 入度条件：根节点的入度为000，其余节点的入度均为111。

等价地，一个有nnn个节点（n>0n>0n>0）的有向图是树，当且仅当：

• 没有重复边和自环。
• 恰好有一个节点的入度为000。
• 其他节点的入度均为111。
• 图是弱连通的（因为从根可到所有节点，自然弱连通）。

本题中的空图（没有任何边）视为一棵树（空树）。

解题思路

数据结构

• 使用map<int, set<int>>存储邻接表，方便检测重复边。
• 使用map<int, int>统计每个节点的入度。
• 使用set<int>记录所有出现过的节点。

读入与预处理

对于每一条边u→vu \to vu→v：

• 若出现重复边（即edges[u]中已包含vvv）或自环（u=vu = vu=v），则标记isTree = false，但继续读入其余边。
• 将vvv的入度加111。
• 将uuu和vvv加入节点集合。

判断流程

1. 若边集合为空（即没有读取到任何边），则该图为空树，直接判定为树。
2. 否则，找到入度为000的节点作为根。若有多个或没有，则不是树。
3. 从根开始进行广度优先搜索（或深度优先搜索），遍历所有可达节点：
   • 若遇到已经访问过的节点，则存在环，不是树。
   • 遍历结束后，若访问到的节点数不等于总节点数，则图不连通，不是树。
4. 若以上检查均通过，则是树。

注意：入度条件在找根和 BFS 过程中已被隐式检查。若某个非根节点入度>1>1>1，则在BFS\texttt{BFS}BFS中该节点会被多次入队，第二次访问时会被检测为环，因此会判定为非树。若某个节点入度为000且不是根，则它无法从根到达，导致不连通，也会判定为非树。

复杂度分析

• 设边数为mmm，节点数为nnn。
• 读入过程：O(m)O(m)O(m)。
• 查找根：O(n)O(n)O(n)。
• 广度优先搜索：O(n+m)O(n + m)O(n+m)。
• 总体时间复杂度O(n+m)O(n + m)O(n+m)，空间复杂度O(n+m)O(n + m)O(n+m)。

代码实现

// Is It A Tree// UVa ID: 615// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intfrom,to,cases=0;while(cin>>from>>to){if(from<0)break;boolisTree=true;map<int,set<int>>edges;map<int,int>degrees;set<int>nodes;while(from>0){if(edges[from].find(to)!=edges[from].end()||from==to)isTree=false;edges[from].insert(to);degrees[to]++;nodes.insert(from),nodes.insert(to);cin>>from>>to;}if(edges.size()==0)isTree=true;else{intstart;for(autonode:nodes)if(degrees.find(node)==degrees.end()){start=node;break;}set<int>visited;queue<int>unvisited;unvisited.push(start);while(!unvisited.empty()){intcurrent=unvisited.front();if(visited.find(current)!=visited.end()){isTree=false;break;}elsevisited.insert(current);unvisited.pop();for(autoedge:edges[current])unvisited.push(edge);}if(visited.size()!=nodes.size())isTree=false;}if(isTree)cout<<"Case "<<++cases<<" is a tree.\n";elsecout<<"Case "<<++cases<<" is not a tree.\n";}return0;}

总结

本题通过检验入度、连通性和无环性来判断有向图是否为树。核心思想是：

• 统计入度，找出唯一的根（入度为000）。
• 从根开始遍历，检查是否有环以及是否所有节点均可达。
• 注意空树也是树。

该解法简单高效，适用于节点编号不连续且范围未知的情况，利用map\texttt{map}map和set\texttt{set}set动态管理数据。