title
给你一个正整数 n ，表示一个 无向 图中的节点数目，节点编号从 1 到 n 。
同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 双向 边。注意给定的图可能是不连通的。
请你将图划分为 m 个组（编号从 1 开始），满足以下要求：
- 图中每个节点都只属于一个组。
- 图中每条边连接的两个点
[ai, bi]，如果ai属于编号为x的组，bi属于编号为y的组，那么|y - x| = 1。
请你返回最多可以将节点分为多少个组（也就是最大的 m ）。如果没办法在给定条件下分组，请你返回 -1 。
示例 1：
输入：n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
输出：4
解释：如上图所示，
- 节点 5 在第一个组。
- 节点 1 在第二个组。
- 节点 2 和节点 4 在第三个组。
- 节点 3 和节点 6 在第四个组。
所有边都满足题目要求。
如果我们创建第五个组，将第三个组或者第四个组中任何一个节点放到第五个组，至少有一条边连接的两个节点所属的组编号不符合题目要求。
示例 2：
输入：n = 3, edges = [[1,2],[2,3],[3,1]]
输出：-1
解释：如果我们将节点 1 放入第一个组，节点 2 放入第二个组，节点 3 放入第三个组，前两条边满足题目要求，但第三条边不满足题目要求。
没有任何符合题目要求的分组方式。
提示：
1 <= n <= 5001 <= edges.length <= 104edges[i].length == 21 <= ai, bi <= nai != bi- 两个点之间至多只有一条边。
solution
二分图才可以分组 / 也可以通过bfs后，比较和start点距离判断，a<->b, 则dis[a]!=dis[b]才可以分组
class Graph:
def bfs(graph, start):
'''
:param graph: collection.defaultdict(list)
:param start: start point
:return:
'''
q = collections.deque()
q.append(start)
visit = set()
visit.add(start)
level = 0
while len(q):
level += 1
for _ in range(len(q)):
u = q.popleft()
for v in graph[u]:
if v not in visit:
visit.add(v)
q.append(v)
return visit, level
'''
划分连同分量, 返回每个联通分量的点list，可以多个联通分量
'''
def groups(self, points, graph) -> List[List[int]]:
groups = []
total_visit = set()
for i in points:
visit = set()
def dfs(u):
nonlocal visit
visit.add(u)
for v in graph[u]:
if v not in visit:
dfs(v)
if i not in total_visit:
dfs(i)
if visit:
for l in visit:
total_visit.add(l)
groups.append(list(visit))
return groups
# 判断是否是二分图，input可以是多个子连通图。graph: 链接表
def isBipartite(self, graph) -> bool:
ans = True
color = collections.defaultdict(int)
n = len(graph)
def dfs(i):
nonlocal ans
if not ans:
return
if color[i] == 0:
color[i] = 1
cur = color[i]
for neighbor in graph[i]:
if color[neighbor] == cur:
ans = False
break
if color[neighbor] == 0:
color[neighbor] = 2 if cur == 1 else 1
dfs(neighbor)
for i in range(n):
if color[i] == 0:
dfs(i)
# print(color)
return ans
class Solution:
def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
graph = collections.defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# 二分图才可以分组
if not Graph().isBipartite(graph):
return -1
# 划分联通分量
groups = Graph().groups(range(1, n + 1), graph)
ans = 0
for group in groups:
t = 0
# 对联通分量的每个节点用bfs求最大长度
for i in group:
t = max(t, Graph.bfs(graph, i)[1])
ans += t
return ans