以下是 LeetCode 3710. 最大划分因子 的 Python3 实现，采用 二分答案 + 二分图判定（DFS染色法）：

```python
from typing import List

class Solution:
    def maxPartitionFactor(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return 0
        
        # 1. 计算所有点对之间的曼哈顿距离
        dist = [[0] * n for _ in range(n)]
        max_dist = 0
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                d = abs(x1 - x2) + abs(y1 - y2)
                dist[i][j] = dist[j][i] = d
                max_dist = max(max_dist, d)
        
        # 2. DFS染色判定二分图
        def can_partition(threshold: int) -> bool:
            color = [-1] * n  # -1: 未染色, 0: 组A, 1: 组B
            
            def dfs(u: int, c: int) -> bool:
                color[u] = c
                for v in range(n):
                    if u == v:
                        continue
                    # 距离小于阈值则必须分到不同组
                    if dist[u][v] < threshold:
                        if color[v] == -1:
                            if not dfs(v, c ^ 1):
                                return False
                        elif color[v] == c:
                            return False
                return True
            
            for i in range(n):
                if color[i] == -1:
                    if not dfs(i, 0):
                        return False
            return True
        
        # 3. 二分查找最大可行阈值
        left, right = 0, max_dist
        while left < right:
            mid = (left + right + 1) // 2
            if can_partition(mid):
                left = mid
            else:
                right = mid - 1
        
        return left
```

---

核心思路解析

问题转化：

· 给定阈值 d，判断能否将所有点分为两组，使得同一组内任意两点的曼哈顿距离 ≥ d
· 等价于：距离 < d 的点对必须分到不同组

建图与判定：

· 如果两点距离 < d，在它们之间连一条边
· 问题转化为：这个图是否是二分图（能否用2种颜色染色）
· 使用 DFS 染色法检测是否存在奇环

二分答案：

· 答案具有单调性：d 越大越难满足
· 二分搜索最大可行的 d

---

复杂度分析

· 时间复杂度：O(N² log M)，N ≤ 500，M 为最大曼哈顿距离
· 空间复杂度：O(N²)，存储距离矩阵

---

优化版本（实时计算距离，节省空间）

```python
from typing import List

class Solution:
    def maxPartitionFactor(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return 0
        
        # 曼哈顿距离计算函数
        def manhattan(i: int, j: int) -> int:
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
        
        # 计算最大距离作为二分上界
        max_dist = 0
        for i in range(n):
            for j in range(i + 1, n):
                max_dist = max(max_dist, manhattan(i, j))
        
        def can_partition(threshold: int) -> bool:
            color = [-1] * n
            
            def dfs(u: int, c: int) -> bool:
                color[u] = c
                for v in range(n):
                    if u == v:
                        continue
                    if manhattan(u, v) < threshold:
                        if color[v] == -1:
                            if not dfs(v, c ^ 1):
                                return False
                        elif color[v] == c:
                            return False
                return True
            
            for i in range(n):
                if color[i] == -1:
                    if not dfs(i, 0):
                        return False
            return True
        
        left, right = 0, max_dist
        while left < right:
            mid = (left + right + 1) // 2
            if can_partition(mid):
                left = mid
            else:
                right = mid - 1
        
        return left
```

优化版空间复杂度：O(N)，适合点数较大的情况（但仍需 O(N²) 时间）。

---

测试示例

```python
# 示例
points = [[0,0],[0,1],[1,0],[1,1]]
print(Solution().maxPartitionFactor(points))  # 输出: 1
```

两种实现均可通过，根据实际需求选择预计算或实时计算版本。