Hard
题目描述
给你一个二维整数数组 edges，表示一个有 n 个节点的无向图，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间有一条边。
构造一个满足以下条件的二维网格：
- 网格的单元格包含从 0 到 n - 1 的所有节点，每个节点恰好出现一次。
- 当且仅当两个节点在
edges中有边连接时，它们才应该在网格中相邻（水平或垂直相邻）。
题目保证给定的 edges 可以形成满足条件的二维网格。
返回满足上述条件的二维整数数组。如果有多个解，返回其中任何一个。
示例 1：
输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]
输出：[[3,1],[2,0]]
示例 2：
输入：n = 5, edges = [[0,1],[1,3],[2,3],[2,4]]
输出：[[4,2,3,1,0]]
示例 3：
输入：n = 9, edges = [[0,1],[0,4],[0,5],[1,7],[2,3],[2,4],[2,5],[3,6],[4,6],[4,7],[6,8],[7,8]]
输出：[[8,6,3],[7,4,2],[1,0,5]]
约束：
2 <= n <= 5 * 10^41 <= edges.length <= 10^5edges[i] = [ui, vi]0 <= ui < vi < n- 所有边都是不同的
- 输入保证
edges可以形成满足条件的二维网格
解题思路
这道题的核心思路是通过分析节点的度数来确定网格的结构：
度数分析：在二维网格中，角落节点度数为2，边缘节点度数为3，内部节点度数为4。特殊情况下，如果是一行或一列，端点度数为1，中间节点度数为2。
确定网格尺寸：
- 如果存在度数为1的节点，说明是一行，行数为1，列数为n
- 否则，找到度数为2的节点（角落节点），通过BFS确定行列数
构造第一行：
- 从一个角落节点开始，通过BFS找到第一行的所有节点
- 利用度数信息确定下一个节点（在第一行中，除了端点外，其他节点都有一个未访问的邻居在下一行）
逐行构造：
- 对于后续的每一行，通过当前行节点的未访问邻居来构造
- 使用BFS或DFS确保正确的顺序
实现细节：
- 建立邻接表存储图结构
- 使用visited数组标记已访问节点
- 通过度数判断网格的几何形状
这种方法充分利用了网格图的结构特性，时间复杂度主要由图遍历决定，空间复杂度主要用于存储邻接表和结果网格。
代码实现
class Solution {
public:
vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
vector<int> degree(n, 0);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
degree[edge[0]]++;
degree[edge[1]]++;
}
// Find nodes with minimum degree
int minDegree = *min_element(degree.begin(), degree.end());
vector<int> candidates;
for (int i = 0; i < n; i++) {
if (degree[i] == minDegree) {
candidates.push_back(i);
}
}
// If minimum degree is 1, it's a single row
if (minDegree == 1) {
vector<int> row(n);
vector<bool> visited(n, false);
int start = candidates[0];
row[0] = start;
visited[start] = true;
for (int i = 1; i < n; i++) {
for (int neighbor : adj[row[i-1]]) {
if (!visited[neighbor]) {
row[i] = neighbor;
visited[neighbor] = true;
break;
}
}
}
return {row};
}
// Find corner (degree 2) and construct grid
int corner = candidates[0];
vector<bool> visited(n, false);
// Build first row starting from corner
vector<int> firstRow = {corner};
visited[corner] = true;
// Find the direction for first row
int current = corner;
while (true) {
int next = -1;
for (int neighbor : adj[current]) {
if (!visited[neighbor]) {
// Check if this neighbor can be in the same row
// A node is in the same row if adding it doesn't create a vertical connection yet
bool canBeInRow = true;
for (int nn : adj[neighbor]) {
if (!visited[nn] && nn != current) {
// Check if nn could be below neighbor
int commonNeighbors = 0;
for (int cn : adj[nn]) {
if (visited[cn] || cn == neighbor) commonNeighbors++;
}
if (commonNeighbors == 1) {
canBeInRow = true;
break;
}
}
}
if (next == -1) next = neighbor;
else {
// Choose the one that extends the row
if (degree[neighbor] <= degree[next]) {
next = neighbor;
}
}
}
}
if (next == -1) break;
firstRow.push_back(next);
visited[next] = true;
current = next;
if (degree[current] == 2) break; // reached another corner
}
int cols = firstRow.size();
int rows = n / cols;
vector<vector<int>> result(rows, vector<int>(cols));
// Fill first row
for (int j = 0; j < cols; j++) {
result[0][j] = firstRow[j];
}
// Build remaining rows
for (int i = 1; i < rows; i++) {
for (int j = 0; j < cols; j++) {
for (int neighbor : adj[result[i-1][j]]) {
if (!visited[neighbor]) {
result[i][j] = neighbor;
visited[neighbor] = true;
break;
}
}
}
}
return result;
}
};
class Solution:
def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
from collections import defaultdict, deque
adj = defaultdict(list)
degree = [0] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
degree[u] += 1
degree[v] += 1
min_degree = min(degree)
candidates = [i for i in range(n) if degree[i] == min_degree]
# If minimum degree is 1, it's a single row
if min_degree == 1:
row = [0] * n
visited = [False] * n
start = candidates[0]
row[0] = start
visited[start] = True
for i in range(1, n):
for neighbor in adj[row[i-1]]:
if not visited[neighbor]:
row[i] = neighbor
visited[neighbor] = True
break
return [row]
# Find corner and construct grid
corner = candidates[0]
visited = [False] * n
# Build first row starting from corner
first_row = [corner]
visited[corner] = True
current = corner
while True:
next_node = -1
for neighbor in adj[current]:
if not visited[neighbor]:
if next_node == -1:
next_node = neighbor
elif degree[neighbor] <= degree[next_node]:
next_node = neighbor
if next_node == -1:
break
first_row.append(next_node)
visited[next_node] = True
current = next_node
if degree[current] == 2: # reached another corner
break
cols = len(first_row)
rows = n // cols
result = [[0] * cols for _ in range(rows)]
# Fill first row
for j in range(cols):
result[0][j] = first_row[j]
# Build remaining rows
for i in range(1, rows):
for j in range(cols):
for neighbor in adj[result[i-1][j]]:
if not visited[neighbor]:
result[i][j] = neighbor
visited[neighbor] = True
break
return result
public class Solution {
public int[][] ConstructGridLayout(int n, int[][] edges) {
List<int>[] adj = new List<int>[n];
int[] degree = new int[n];
for (int i = 0; i < n; i++) {
adj[i] = new List<int>();
}
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
degree[edge[0]]++;
degree[edge[1]]++;
}
int minDegree = degree.Min();
List<int> candidates = new List<int>();
for (int i = 0; i < n; i++) {
if (degree[i] == minDegree) {
candidates.Add(i);
}
}
// If minimum degree is 1, it's a single row
if (minDegree == 1) {
int[] row = new int[n];
bool[] visited = new bool[n];
int start = candidates[0];
row[0] = start;
visited[start] = true;
for (int i = 1; i < n; i++) {
foreach (int neighbor in adj[row[i-1]]) {
if (!visited[neighbor]) {
row[i] = neighbor;
visited[neighbor] = true;
break;
}
}
}
return new int[][] { row };
}
// Find corner and construct grid
int corner = candidates[0];
bool[] visited2 = new bool[n];
// Build first row starting from corner
List<int> firstRow = new List<int> { corner };
visited2[corner] = true;
int current = corner;
while (true) {
int nextNode = -1;
foreach (int neighbor in adj[current]) {
if (!visited2[neighbor]) {
if (nextNode == -1) {
nextNode = neighbor;
} else if (degree[neighbor] <= degree[nextNode]) {
nextNode = neighbor;
}
}
}
if (nextNode == -1) break;
firstRow.Add(nextNode);
visited2[nextNode] = true;
current = nextNode;
if (degree[current] == 2) break; // reached another corner
}
int cols = firstRow.Count;
int rows = n / cols;
int[][] result = new int[rows][];
for (int i = 0; i < rows; i++) {
result[i] = new int[cols];
}
// Fill first row
for (int j = 0; j < cols; j++) {
result[0][j] = firstRow[j];
}
// Build remaining rows
for (int i = 1; i < rows; i++) {
for (int j = 0; j < cols; j++) {
foreach (int neighbor in adj[result[i-1][j]]) {
if (!visited2[neighbor]) {
result[i][j] = neighbor;
visited2[neighbor] = true;
break;
}
}
}
}
return result;
}
}
var constructGridLayout = function(n, edges) {
const adj = Array.from({length: n}, () => []);
const degree = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
degree[u]++;
degree[v]++;
}
const minDegree = Math.min(...degree);
const candidates = [];
for (let i = 0; i < n; i++) {
if (degree[i]
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |