HDU 1325 Is It A Tree?

传送门

这个题是判断是否为树。 树的边是有向的，树也可以为空。 代码里面，directed_V指 子结点集，V指结点集，E指边集。 还有一个坑，最后结束标志是负数而不一定是-1。

---

（19年5月9日）这道题和HDU 1272的区别在于，这道题在无环连通图之上、还要判断边的方向是否符合树结构。（这道题考虑全面，没钻空子。。）

1. 首先按照无向图处理，先判断它是不是 无环连通图

因为树的基图肯定是无环连通图。 判断过程参考这个总结。因为只需要判断是不是 无环连通图，并不需要纠结它是 有环连通 还是 有环非连通。所以并查集中间发现有环就可以直接退出了。

2. 然后判断是不是树结构

首先定义一下这道题给的树结构。 树要么为空，要么为一个符合以下性质的无环连通图：

有且仅有一个入度为0的点（这个点就是根），其余点（也可以没有其余点、只有根）的入度都为1。

定义结束，对点的出度并没有要求。（其实这道题给的输入格式表示不了只有一个根的情况。。）

首先，判空很简单，放在最开始判断就好了。 然后，判断点的入度。一个点若有入度则一定被边指向。而输入给了所有边的序列。可以想到，每条边指向的点都只能被指向这么一次。所以，每条边都应指向不同的点。所以，边的数量应该等于被指向的点的集合的大小。 由于已经是无环连通图了，所以 边数 = 点数 - 1，而每条边都一一对应着一个入度为1的点，那么，最后剩下的那个点就是入度为0的点、就是根。

总结

下式从左往右显然成立，而上述第二点证明了下式从右往左也是成立的，所以下式成立。 在代码中，实际上先对第二点进行了判断。 $$G是树⟺(V=\varnothing )or(G的基图是无环连通图and|directed\_V|=|E|)$$

#include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <unordered_set> using namespace std; const int MAXN = 1e6; // 并没给范围 int pre[MAXN]; int conn; // 并查集记录的那个数据，其实代表了去掉环的边集大小，上限是|V|-1 int CASE = 0; struct Edge { int from, to; }; vector<Edge> E; // 边集 Edge unordered_set<int> V; // 结点集 Vertex unordered_set<int> directed_V; // 入度大于0的 / 被指向的 结点的集合 void init() { memset(pre, -1, sizeof pre); conn = 0; CASE++; E.clear(); V.clear(); directed_V.clear(); } int f(int n) { if (pre[n] < 0) return n; return pre[n] = f(pre[n]); } bool u(int n1, int n2) { int f1 = f(n1); int f2 = f(n2); if (f1 == f2) return false; // 实锤有环 if (pre[f1] <= pre[f2]) { pre[f1] += pre[f2]; pre[f2] = f1; } else { pre[f2] += pre[f1]; pre[f1] = f2; } return true; } void judge() { if (E.empty()) // 树为空 { printf("Case %d is a tree.\n", CASE); return; } if (E.size() != directed_V.size()) // 判定重指，提前判断 { printf("Case %d is not a tree.\n", CASE); return; } for (int i = 0; i < E.size(); i++) { if (!u(E[i].from, E[i].to)) { printf("Case %d is not a tree.\n", CASE); // 有环就可以直接退出了 return; } else conn++; if (conn == V.size() - 1) break; } if (conn == V.size() - 1 && E.size() == V.size() - 1) // 第一个条件判定连通，第二个条件判定无环 printf("Case %d is a tree.\n", CASE); else printf("Case %d is not a tree.\n", CASE); } int main() { int a, b; init(); for (; ~scanf("%d%d", &a, &b);) { if (a < 0) break; // 坑！ if (a == 0) { judge(); init(); continue; } E.push_back(Edge{ a,b }); V.insert(a); V.insert(b); directed_V.insert(b); // } return 0; }