LeetCode 3311. 构造符合图结构的二维矩阵

LeetCode 3311. 构造符合图结构的二维矩阵

给你一个二维整数数组 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 * 104
1 <= edges.length <= 105
edges[i] = [ui, vi]
0 <= ui < vi < n
树中的边互不相同。
输入保证 edges 可以形成一个符合上述条件的二维矩阵。

建图、图的遍历

class Node:
    def __init__(self, val):
        self.val = val
        self.next = []


class Solution:
    def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        node_mapping = {}
        for u, v in edges:
            if u not in node_mapping:
                node_mapping[u] = Node(u)
            if v not in node_mapping:
                node_mapping[v] = Node(v)
            u_node, v_node = node_mapping[u], node_mapping[v]
            u_node.next.append(v_node)
            v_node.next.append(u_node)

        # 先找出拥有最少连接点的结点，一个或两个
        m = 0
        for i in node_mapping:
            if len(node_mapping[m].next) > len(node_mapping[i].next):
                m = i

        # 1.有只有一个连接点的结点那么矩阵一定是一行
        visted = set()
        res = []
        if len(node_mapping[m].next) == 1:
            node = node_mapping[m]
            while node:
                res.append(node.val)
                visted.add(node.val)
                for _node in node.next:
                    if _node.val not in visted:
                        node = _node
                if node.val in visted:
                    node = None
            return [res]

        # 2.其他情况就是一个矩阵
        visted = set()
        res = []
        if len(node_mapping[m].next) == 2:
            # 先分析出矩阵第一行
            node = node_mapping[m]
            layer = []
            while node:
                layer.append(node.val)
                visted.add(node.val)
                for _node in node.next:
                    if _node.val not in visted:
                        # 第一行除第一个和最后一个点外都连接了3个点
                        if len(_node.next) == 3:
                            node = _node
                        # 最后一个点连接了2个点
                        elif len(_node.next) == 2:
                            layer.append(_node.val)
                            visted.add(_node.val)
                            node = None
                            break
            res.append(layer)

            # 从第二行开始每次遍历上一行的结果找到下一行就行
            flag = True
            while flag:
                layern = res[-1]
                new_layer = []
                for i in layern:
                    flag = False
                    node = node_mapping[i]
                    for _node in node.next:
                        if _node.val not in visted:
                            new_layer.append(_node.val)
                            visted.add(_node.val)
                            flag = True
                            break
                if new_layer:
                    res.append(new_layer)
            return res