仙人掌图森林子图最大边数求解及代码异常排查

现有代码的核心问题 #

1. 原图边数计算错误 #

无向图的邻接表中，每条边会被两个顶点各存储一次，因此直接求和邻接表长度得到的是两倍的实际边数。测试用例中sum结果为18，除以2后才是正确的9条边。

2. 函数逻辑不符合题目要求 #

原函数的逻辑是遍历每个顶点做DFS，寻找图中最大的单棵树的边数，完全忽略了：

• 必须保留顶点0和1的边的约束
• 森林子图的最大边数应该是所有连通分量的树边数之和（公式：总顶点数 - 连通分量数），而非单棵树的最大边数

需求澄清与修正思路 #

根据题目描述，我们需要：

1. 强制保留0-1边（如果存在）
2. 构建无环的森林子图，最大化边数（即最小化连通分量数）

对于给定的测试用例（3个以顶点2为公共点的三角形：0-1-2、2-3-4、2-5-6），满足约束的最大森林子图应该是一棵包含所有7个顶点的树（边数为6），因为可以保留0-1边，再通过2连接其他所有顶点且不形成环。但你提到预期结果为3，这可能是将“森林”误理解为匹配子图（每个顶点最多连一条边），如果是这种情况，最大匹配确实是3（0-1、3-4、5-6）。

以下分别提供两种需求下的修正代码：

情况1：正确森林子图（无环，最大化边数） #

def max_edges_in_forest(cactus_graph, num_vertices, required_edge=None):
    visited = [False] * num_vertices
    num_components = 0
    num_edges = 0

    def dfs(vertex):
        nonlocal num_edges
        visited[vertex] = True
        for neighbor in cactus_graph[vertex]:
            if not visited[neighbor]:
                num_edges += 1
                dfs(neighbor)
    
    # 处理必须保留的边：0-1
    if required_edge is not None:
        u, v = required_edge
        if v in cactus_graph[u]:
            # 标记两个顶点已访问，归为同一个连通分量
            visited[u] = True
            visited[v] = True
            num_components += 1
            num_edges += 1
            dfs(u)
            dfs(v)
    
    # 遍历剩余未访问的顶点
    for v in range(num_vertices):
        if not visited[v]:
            num_components += 1
            dfs(v)
    
    return num_edges

# Example usage
cactus_graph = [[1,2], [0,2], [0,1,3,4,5,6], [2,4],[2,3],[2,6],[2,5]]
num_vertices = 7
# 计算原图实际边数
actual_num_edges = sum(len(adj_list) for adj_list in cactus_graph) // 2
# 传入必须保留的边(0,1)
max_edges = max_edges_in_forest(cactus_graph, num_vertices, required_edge=(0,1))
print("Number of edges in the cactus graph:", actual_num_edges)
print("Maximum number of edges in the forest subgraph:", max_edges)

输出结果：

Number of edges in the cactus graph: 9
Maximum number of edges in the forest subgraph: 6

情况2：匹配子图（每个顶点最多一条边，保留0-1边） #

如果你的实际需求是求最大匹配（即每个顶点度数不超过1的森林），代码如下：

def max_matching_with_required_edge(cactus_graph, num_vertices, required_edge):
    visited = [False] * num_vertices
    u, v = required_edge
    # 必须保留0-1边，先标记这两个顶点已匹配
    if v not in cactus_graph[u]:
        return 0
    visited[u] = True
    visited[v] = True
    match_count = 1

    def dfs(vertex):
        nonlocal match_count
        visited[vertex] = True
        for neighbor in cactus_graph[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = True
                match_count += 1
                # 跳过邻居的其他邻接顶点
                return
        return
    
    for v in range(num_vertices):
        if not visited[v]:
            dfs(v)
    
    return match_count

# Example usage
cactus_graph = [[1,2], [0,2], [0,1,3,4,5,6], [2,4],[2,3],[2,6],[2,5]]
num_vertices = 7
actual_num_edges = sum(len(adj_list) for adj_list in cactus_graph) // 2
max_match = max_matching_with_required_edge(cactus_graph, num_vertices, required_edge=(0,1))
print("Number of edges in the cactus graph:", actual_num_edges)
print("Maximum number of edges in the matching subgraph:", max_match)

输出结果：

Number of edges in the cactus graph: 9
Maximum number of edges in the matching subgraph: 3

内容的提问来源于stack exchange，提问作者Gabriel Rigo