Hard
题目描述
给你一个正整数 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- 任何一对顶点之间最多只有一条边。
解题思路
解题思路
这道题的核心在于理解题目要求：相邻节点必须在相邻的组中，即组号相差1。
关键观察：
- 如果图不是二分图，则无解。因为相邻节点组号相差1，意味着相邻节点必须在不同奇偶性的组中
- 对于每个连通分量，可以独立求解，最终答案是各分量答案的和
- 对于一个连通分量，固定某个节点为起始组（组1），其他节点的组号就由BFS层数决定
算法步骤：
- 二分图检测：使用DFS或BFS给节点染色，检查是否存在奇数环
- 连通分量分解：将图分解为多个连通分量
- 求解每个分量：对每个分量，尝试以每个节点为起点做BFS，记录最大深度。取所有起点中的最大值
为什么要尝试所有起点？ 因为不同的起点可能产生不同的BFS树结构，导致不同的最大深度。我们要找到能产生最多组数的那个起点。
优化思考：
- 可以只在每个连通分量中尝试部分关键节点作为起点
- 但为了保证正确性，最安全的方法是尝试所有节点
代码实现
class Solution {
public:
int magnificentSets(int n, vector<vector<int>>& edges) {
vector<vector<int>> graph(n + 1);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<int> color(n + 1, -1);
vector<vector<int>> components;
// 检查是否为二分图并找到所有连通分量
for (int i = 1; i <= n; i++) {
if (color[i] == -1) {
vector<int> component;
if (!dfs(i, 0, graph, color, component)) {
return -1;
}
components.push_back(component);
}
}
int totalGroups = 0;
for (auto& component : components) {
int maxGroups = 0;
for (int node : component) {
maxGroups = max(maxGroups, bfs(node, graph, n));
}
totalGroups += maxGroups;
}
return totalGroups;
}
private:
bool dfs(int node, int c, vector<vector<int>>& graph, vector<int>& color, vector<int>& component) {
color[node] = c;
component.push_back(node);
for (int neighbor : graph[node]) {
if (color[neighbor] == -1) {
if (!dfs(neighbor, 1 - c, graph, color, component)) {
return false;
}
} else if (color[neighbor] == c) {
return false;
}
}
return true;
}
int bfs(int start, vector<vector<int>>& graph, int n) {
vector<int> dist(n + 1, -1);
queue<int> q;
q.push(start);
dist[start] = 1;
int maxDist = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
maxDist = max(maxDist, dist[neighbor]);
q.push(neighbor);
}
}
}
return maxDist;
}
};
class Solution:
def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
from collections import defaultdict, deque
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
color = [-1] * (n + 1)
components = []
def dfs(node, c, component):
color[node] = c
component.append(node)
for neighbor in graph[node]:
if color[neighbor] == -1:
if not dfs(neighbor, 1 - c, component):
return False
elif color[neighbor] == c:
return False
return True
# 检查是否为二分图并找到所有连通分量
for i in range(1, n + 1):
if color[i] == -1:
component = []
if not dfs(i, 0, component):
return -1
components.append(component)
def bfs(start):
dist = [-1] * (n + 1)
queue = deque([start])
dist[start] = 1
max_dist = 1
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if dist[neighbor] == -1:
dist[neighbor] = dist[node] + 1
max_dist = max(max_dist, dist[neighbor])
queue.append(neighbor)
return max_dist
total_groups = 0
for component in components:
max_groups = 0
for node in component:
max_groups = max(max_groups, bfs(node))
total_groups += max_groups
return total_groups
public class Solution {
public int MagnificentSets(int n, int[][] edges) {
var graph = new List<int>[n + 1];
for (int i = 0; i <= n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
var color = new int[n + 1];
Array.Fill(color, -1);
var components = new List<List<int>>();
for (int i = 1; i <= n; i++) {
if (color[i] == -1) {
var component = new List<int>();
if (!Dfs(i, 0, graph, color, component)) {
return -1;
}
components.Add(component);
}
}
int totalGroups = 0;
foreach (var component in components) {
int maxGroups = 0;
foreach (int node in component) {
maxGroups = Math.Max(maxGroups, Bfs(node, graph, n));
}
totalGroups += maxGroups;
}
return totalGroups;
}
private bool Dfs(int node, int c, List<int>[] graph, int[] color, List<int> component) {
color[node] = c;
component.Add(node);
foreach (int neighbor in graph[node]) {
if (color[neighbor] == -1) {
if (!Dfs(neighbor, 1 - c, graph, color, component)) {
return false;
}
} else if (color[neighbor] == c) {
return false;
}
}
return true;
}
private int Bfs(int start, List<int>[] graph, int n) {
var dist = new int[n + 1];
Array.Fill(dist, -1);
var queue = new Queue<int>();
queue.Enqueue(start);
dist[start] = 1;
int maxDist = 1;
while (queue.Count > 0) {
int node = queue.Dequeue();
foreach (int neighbor in graph[node]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
maxDist = Math.Max(maxDist, dist[neighbor]);
queue.Enqueue(neighbor);
}
}
}
return maxDist;
}
}
var magnificentSets = function(n, edges) {
const graph = Array(n + 1).fill(null).map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
// Check if graph is bipartite using DFS
const color = Array(n + 1).fill(-1);
function isBipartite(start) {
const stack = [start];
color[start] = 0;
while (stack.length > 0) {
const node = stack.pop();
for (const neighbor of graph[node]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[node];
stack.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false;
}
}
}
return true;
}
// Find connected components and check bipartiteness
const visited = Array(n + 1).fill(false);
const components = [];
for (let i = 1; i <= n; i++) {
if (!visited[i]) {
const component = [];
const queue = [i];
visited[i] = true;
if (!isBipartite(i)) {
return -1;
}
while (queue.length > 0) {
const node = queue.shift();
component.push(node);
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
components.push(component);
}
}
// For each component, find maximum groups using BFS
function maxGroups(component) {
let maxLevels = 0;
for (const start of component) {
const levels = Array(n + 1).fill(-1);
const queue = [start];
levels[start] = 1;
let currentMax = 1;
while (queue.length > 0) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (component.includes(neighbor)) {
if (levels[neighbor] === -1) {
levels[neighbor] = levels[node] + 1;
currentMax = Math.max(currentMax, levels[neighbor]);
queue.push(neighbor);
}
}
}
}
maxLevels = Math.max(maxLevels, currentMax);
}
return maxLevels;
}
let totalGroups = 0;
for (const component of components) {
totalGroups += maxGroups(component);
}
return totalGroups;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n × (n + m))，其中 n 是节点数，m 是边数。需要对每个连通分量中的每个节点执行一次BFS |
| 空间复杂度 | O(n + m)，用于存储图的邻接表、访问状态和BFS队列 |
相关题目
. Binary Tree Level Order Traversal (Medium)
. Is Graph Bipartite? (Medium)
. Shortest Cycle in a Graph (Hard)