如何计算无向图中形成循环的连通分量？

Question

我正在使用一个无向图，需要确定也是循环的连接组件的数量。循环被定义为一个连通分量，其中每个顶点恰好有两条边，并且该分量至少包含三个顶点。

该图由

n

顶点和

m

边表示。每条边连接两个不同的顶点，并且不存在重复的边。

定义：

1. 无向图:

   • 由两组组成：一组顶点，另一组边。
   • 每条边连接两个不同的顶点 (( u 等式 v )).
   • 任意一对顶点之间至多有一条边。

2. 连接组件：

   • 顶点的子集，该子集中的任何两个顶点都通过路径连接，并且该子集不连接到其之外的任何其他顶点。

3. 循环：

   • 如果满足以下条件，则连通分量是一个循环：
     • 它至少包含 3 个顶点。
     • 每个顶点恰好是 2 条边的一部分。
     • 重新排列其顶点可以形成一个序列，使得第一个顶点连接到第二个顶点，第二个顶点连接到第三个，......，最后一个顶点连接回第一个顶点。

输入：

• 第一行包含两个整数，

  n

  （1 ≤ n ≤ 200,000）和

  m

  （0 ≤ m ≤ 200,000），代表顶点和边的数量。
• 接下来的

  m

  行每行包含两个整数

  u

  和

  v

  ，描述顶点

  u

  和顶点

  v

  之间的边。没有重复的边，并且图是无向的。

输出：

• 单个整数：图中循环的连通分量的数量。

示例：

输入：

17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6

输出：

2

我的尝试：

我实现了以下Python解决方案，该解决方案适用于某些情况，但对于我大学提交平台中的某些隐藏测试用例则失败。这是我使用的代码：

from collections import defaultdict, deque

def count_cycle_components(n, m, edges):
    # Create an adjacency list for the graph
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # Visited array to track visited nodes
    visited = [False] * (n + 1)

    # Helper function to check if a connected component is a cycle
    def is_cycle_component(node):
        queue = deque([(node, -1)])  # (current node, parent node)
        visited[node] = True
        node_count = 0
        edge_count = 0

        while queue:
            current, parent = queue.popleft()
            node_count += 1
            for neighbor in graph[current]:
                edge_count += 1
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append((neighbor, current))
                elif neighbor != parent:
                    pass  # Neighbor visited and not parent, ignore
        
        # Each edge is counted twice in an undirected graph
        edge_count //= 2

        # Check if the connected component is a cycle
        return node_count >= 3 and edge_count == node_count

    cycle_count = 0

    # Iterate through all nodes to find connected components
    for node in range(1, n + 1):
        if not visited[node]:
            if is_cycle_component(node):
                cycle_count += 1

    return cycle_count

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().splitlines()

    # Read the number of vertices and edges
    n, m = map(int, data[0].split())
    # Read the edges
    edges = [tuple(map(int, line.split())) for line in data[1:]]

    # Output the number of cycle components
    print(count_cycle_components(n, m, edges))

知道为什么这段代码对于某些测试用例可能会失败吗？如何纠正或优化来解决这个问题？

Answer 1

我实现了 DFS 方法而不是 BFS。我已经创建了一组已访问的节点，可以防止重新访问节点。这些更改应该会提高算法的性能并确保其通过所有测试用例。让我知道它是否有效。

from collections import defaultdict

def count_cycle_components(n, m, edges):
    # Create an adjacency list for the graph
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def is_cycle_component(node, parent):
        stack = [(node, parent)]
        component_nodes = set()
        edge_count = 0

        while stack:
            current, parent = stack.pop()
            if current in component_nodes:
                continue
            component_nodes.add(current)

            for neighbor in graph[current]:
                edge_count += 1
                if neighbor != parent:
                    stack.append((neighbor, current))

        # Each edge is counted twice in an undirected graph
        edge_count //= 2

        # Check if all nodes in the component have degree 2 and form a cycle
        if len(component_nodes) >= 3 and edge_count == len(component_nodes):
            for node in component_nodes:
                if len(graph[node]) != 2:
                    return False
            return True
        return False

    cycle_count = 0

    # Iterate through all nodes to find connected components
    for node in range(1, n + 1):
        if node not in visited:
            # Mark all nodes in the current component as visited
            component_nodes = set()
            stack = [node]
            while stack:
                current = stack.pop()
                if current not in visited:
                    visited.add(current)
                    component_nodes.add(current)
                    for neighbor in graph[current]:
                        if neighbor not in visited:
                            stack.append(neighbor)

            # Check if the connected component is a cycle
            if is_cycle_component(node, -1):
                cycle_count += 1

    return cycle_count

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().splitlines()

    n, m = map(int, data[0].split())
    edges = [tuple(map(int, line.split())) for line in data[1:]]
    print(count_cycle_components(n, m, edges))