Question

1719. 重构一棵树的方案数

English Version

题目描述

给你一个数组 pairs ，其中 pairs[i] = [xi, yi] ，并且满足：

• pairs 中没有重复元素
• xi < yi

令 ways 为满足下面条件的有根树的方案数：

• 树所包含的所有节点值都在 pairs 中。
• 一个数对 [xi, yi] 出现在 pairs 中 当且仅当 xi 是 yi 的祖先或者 yi 是 xi 的祖先。
• 注意：构造出来的树不一定是二叉树。

两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。

请你返回：

• 如果 ways == 0 ，返回 0 。
• 如果 ways == 1 ，返回 1 。
• 如果 ways > 1 ，返回 2 。

一棵 有根树 指的是只有一个根节点的树，所有边都是从根往外的方向。

我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的 祖先 。根节点没有祖先。

 

示例 1：

输入：pairs = [[1,2],[2,3]]
输出：1
解释：如上图所示，有且只有一个符合规定的有根树。

示例 2：

输入：pairs = [[1,2],[2,3],[1,3]]
输出：2
解释：有多个符合规定的有根树，其中三个如上图所示。

示例 3：

输入：pairs = [[1,2],[2,3],[2,4],[1,5]]
输出：0
解释：没有符合规定的有根树。

 

提示：

• 1 <= pairs.length <= 105
• 1 <= xi < yi <= 500
• pairs 中的元素互不相同。

解法

方法一

class Solution:
  def checkWays(self, pairs: List[List[int]]) -> int:
    g = [[False] * 510 for _ in range(510)]
    v = defaultdict(list)
    for x, y in pairs:
      g[x][y] = g[y][x] = True
      v[x].append(y)
      v[y].append(x)
    nodes = []
    for i in range(510):
      if v[i]:
        nodes.append(i)
        g[i][i] = True
    nodes.sort(key=lambda x: len(v[x]))
    equal = False
    root = 0
    for i, x in enumerate(nodes):
      j = i + 1
      while j < len(nodes) and not g[x][nodes[j]]:
        j += 1
      if j < len(nodes):
        y = nodes[j]
        if len(v[x]) == len(v[y]):
          equal = True
        for z in v[x]:
          if not g[y][z]:
            return 0
      else:
        root += 1
    if root > 1:
      return 0
    return 2 if equal else 1

class Solution {
  public int checkWays(int[][] pairs) {
    boolean[][] g = new boolean[510][510];
    List<Integer>[] v = new List[510];
    Arrays.setAll(v, k -> new ArrayList<>());
    for (int[] p : pairs) {
      int x = p[0], y = p[1];
      g[x][y] = true;
      g[y][x] = true;
      v[x].add(y);
      v[y].add(x);
    }
    List<Integer> nodes = new ArrayList<>();
    for (int i = 0; i < 510; ++i) {
      if (!v[i].isEmpty()) {
        nodes.add(i);
        g[i][i] = true;
      }
    }
    nodes.sort(Comparator.comparingInt(a -> v[a].size()));
    boolean equal = false;
    int root = 0;
    for (int i = 0; i < nodes.size(); ++i) {
      int x = nodes.get(i);
      int j = i + 1;
      for (; j < nodes.size() && !g[x][nodes.get(j)]; ++j)
        ;
      if (j < nodes.size()) {
        int y = nodes.get(j);
        if (v[x].size() == v[y].size()) {
          equal = true;
        }
        for (int z : v[x]) {
          if (!g[y][z]) {
            return 0;
          }
        }
      } else {
        ++root;
      }
    }
    if (root > 1) {
      return 0;
    }
    return equal ? 2 : 1;
  }
}

class Solution {
public:
  int checkWays(vector<vector<int>>& pairs) {
    vector<vector<bool>> g(510, vector<bool>(510));
    vector<vector<int>> v(510);
    for (auto& p : pairs) {
      int x = p[0], y = p[1];
      g[x][y] = g[y][x] = 1;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    vector<int> nodes;
    for (int i = 1; i <= 500; ++i) {
      if (v[i].size()) {
        nodes.push_back(i);
        g[i][i] = 1;
      }
    }
    sort(nodes.begin(), nodes.end(), [&](int x, int y) -> bool { return v[x].size() < v[y].size(); });
    bool equal = 0;
    int root = 0;
    for (int i = 0; i < nodes.size(); ++i) {
      int x = nodes[i];
      int j = i + 1;
      for (; j < nodes.size() && !g[x][nodes[j]]; ++j)
        ;
      if (j < nodes.size()) {
        int y = nodes[j];
        if (v[x].size() == v[y].size()) equal = 1;
        for (int z : v[x])
          if (!g[y][z])
            return 0;
      } else
        ++root;
    }
    if (root > 1) return 0;
    if (equal) return 2;
    return 1;
  }
};

func checkWays(pairs [][]int) int {
  g := make([][]bool, 510)
  v := make([][]int, 510)
  for i := range g {
    g[i] = make([]bool, 510)
  }
  for _, p := range pairs {
    x, y := p[0], p[1]
    g[x][y] = true
    g[y][x] = true
    v[x] = append(v[x], y)
    v[y] = append(v[y], x)
  }
  var nodes []int
  for i := 1; i <= 500; i++ {
    if len(v[i]) > 0 {
      nodes = append(nodes, i)
      g[i][i] = true
    }
  }
  sort.Slice(nodes, func(i, j int) bool {
    return len(v[nodes[i]]) < len(v[nodes[j]])
  })
  equal := false
  root := 0
  for i, x := range nodes {
    j := i + 1
    for ; j < len(nodes) && !g[x][nodes[j]]; j++ {
    }
    if j < len(nodes) {
      y := nodes[j]
      if len(v[x]) == len(v[y]) {
        equal = true
      }
      for _, z := range v[x] {
        if !g[y][z] {
          return 0
        }
      }
    } else {
      root++
    }
  }
  if root > 1 {
    return 0
  }
  if equal {
    return 2
  }
  return 1
}