题目描述
给定一个数组 pairs
,其中 pairs[i] = [x_i, y_i]
,并且满足:
pairs
中没有重复元素x_i
<y_i
令 ways
为满足下面条件的有根树的方案数:
- 树所包含的所有节点值都在
pairs
中。 - 一个数对
[x_i, y_i]
出现在pairs
中 当且仅当x_i
是y_i
的祖先或者y_i
是x_i
的祖先。
注意:构造出来的树不一定是二叉树。
两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。
请返回:
- 如果
ways == 0
,返回0
。 - 如果
ways == 1
,返回1
。 - 如果
ways > 1
,返回2
。
一棵 有根树 指的是只有一个根节点的树,所有边都是从根往外的方向。
我们称从根到一个节点路径上的任意一个节点(除去节点本身)都是该节点的 祖先。根节点没有祖先。
样例
输入:pairs = [[1,2],[2,3]]
输出:1
解释:如上图所示,有且只有一个符合规定的有根树。
输入:pairs = [[1,2],[2,3],[1,3]]
输出:2
解释:有多个符合规定的有根树,其中三个如上图所示。
输入:pairs = [[1,2],[2,3],[2,4],[1,5]]
输出:0
解释:没有符合规定的有根树。
限制
1 <= pairs.length <= 10^5
1 <= x_i < y_i <= 500
pairs
中的元素互不相同。
算法
(构造) $O(n^2 + m)$
- 一个显而易见的递归解决方法:
- 给定一组点和这些点的关系,找到其中度数(参与关系)最多的点(可能有多个),并且其度数等于点的个数减 1,度数最大的点就是这组点的根节点(多个点的情况下任意一个都可以当做根)。
- 去掉度数最大的点(点集)和其关联的边,剩余的点和边通过并查集再分为若干个子集合,递归处理。
- 中途如果找不到根节点,则返回 0。
- 如果存在一个点集有多个根节点,则返回 2。
- 以上算法直接递归实现的时间复杂度为 $O(nm)$,超时。
- 考虑另一种实现方式,先试图找到一棵符合要求的树。
- 先将所有点按照度数从大到小排序。
- 排名第一的点当做根节点。按照排序的结果,依次添加到树中。
- 添加时,倒序枚举已经在树中的点。如果该祖先关系存在,则令当前点的父节点为枚举的点。如果没有边连接到已经在树中的点,则返回 0。
- 枚举树上任意一个点,判断其所有的祖先关系是否合法。最后判断关系的总数是否等于给定关系的总数。
- 均合法的情况下,如果存在一个关系,其两个点的度数相同,说明有多种方式,返回 2。否则返回 1。
时间复杂度
- 初始化的时间复杂度为 $O(m)$,构造和判定答案的时间复杂度为 $O(n^2)$。
- 故总时间复杂度为 $O(n^2 + m)$。
空间复杂度
- 需要 $O(n^2)$ 的额外空间存储所有关系。
C++ 代码
#define N 510
class Solution {
public:
int checkWays(vector<vector<int>>& pairs) {
bool map[N][N];
int deg[N];
memset(deg, 0, sizeof(deg));
memset(map, false, sizeof(map));
unordered_set<int> s;
for (const auto &e : pairs) {
map[e[0]][e[1]] = true; map[e[1]][e[0]] = true;
deg[e[0]]++; deg[e[1]]++;
s.insert(e[0]); s.insert(e[1]);
}
vector<int> v;
for (int x : s)
v.push_back(x);
sort(v.begin(), v.end(), [&](int x, int y) {
return deg[x] > deg[y];
});
int fa[N];
memset(fa, -1, sizeof(fa));
for (int i = 1; i < v.size(); i++) {
for (int j = i - 1; j >= 0; j--)
if (map[v[j]][v[i]]) {
fa[v[i]] = v[j];
break;
}
if (fa[v[i]] == -1)
return 0;
}
int counter = 0;
for (int i = 0; i < v.size(); i++) {
int j = v[i];
while (fa[j] != -1) {
if (!map[j][fa[j]])
return 0;
counter++;
j = fa[j];
}
}
if (counter != pairs.size())
return 0;
for (const auto &e : pairs)
if (deg[e[0]] == deg[e[1]])
return 2;
return 1;
}
};