封锁阳光大学 - 最少河蟹数量

题目描述

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由 $n$ 个点构成的无向图，$n$ 个点之间由 $m$ 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

输入格式

第一行两个正整数，表示节点数和边数。 接下来 $m$ 行，每行两个整数 $u,v$，表示点 $u$ 到点 $v$ 之间有道路相连。

输出格式

仅一行如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。

样例 #1

样例输入 #1

3 3
1 2
1 3
2 3

样例输出 #1

Impossible

样例 #2

样例输入 #2

3 2
1 2
2 3

样例输出 #2

1

提示

【数据规模】
对于 $100%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，保证没有重边。

解题思路

题目要求最少需要多少只河蟹可以封锁所有道路并且不发生冲突。根据题目中的条件，我们可以得知以下几个规律：

1. 如果两个点之间有道路相连，那么这两个点之间的道路必须被河蟹封锁。
2. 如果两个点之间有多条道路相连，那么这些道路必须被河蟹封锁。
3. 如果两个点之间有多条道路相连，并且这些道路之间没有交叉，那么这些道路的封锁顺序不会影响封锁的结果。

根据以上规律，我们可以将问题转化为求无向图中的割点个数。割点是指一个点，如果将该点从图中移除，会导致图中的连通分量数量增加。在本题中，割点就代表一个点被河蟹封锁后，会导致无法通过的道路数量增加。

具体算法如下：

1. 使用深度优先搜索（DFS）遍历图，找到所有的割点。
2. 如果图中没有割点，那么可以通过封锁所有的道路而不发生冲突，输出河蟹的最少数量为 1。
3. 如果图中有割点，那么无法通过封锁所有的道路而不发生冲突，输出 'Impossible'。

代码实现

def dfs(graph, node, parent, visited, low, disc, is_cut_vertex, time):
    # 标记当前节点为已访问
    visited[node] = True

    # 初始化节点的发现时间和最早发现时间
    disc[node] = time
    low[node] = time
    time += 1

    # 记录节点的子节点数量
    children = 0

    # 遍历当前节点的邻居节点
    for neighbor in graph[node]:
        # 如果邻居节点未被访问，则进行深度优先搜索
        if not visited[neighbor]:
            parent[neighbor] = node
            children += 1
            dfs(graph, neighbor, parent, visited, low, disc, is_cut_vertex, time)
            
            # 更新当前节点的最早发现时间
            low[node] = min(low[node], low[neighbor])

            # 如果当前节点不是根节点，并且满足割点的条件
            if parent[node] != -1 and low[neighbor] >= disc[node]:
                is_cut_vertex[node] = True
            
            # 如果当前节点是根节点，并且有两个以上的子节点
            if parent[node] == -1 and children > 1:
                is_cut_vertex[node] = True
        # 如果邻居节点已经被访问过，并且不是当前节点的父节点
        elif neighbor != parent[node]:
            # 更新当前节点的最早发现时间
            low[node] = min(low[node], disc[neighbor])

def find_cut_vertices(graph, n):
    # 初始化访问过的节点、发现时间和最早发现时间
    visited = [False] * n
    disc = [float('inf')] * n
    low = [float('inf')] * n

    # 初始化父节点和割点
    parent = [-1] * n
    is_cut_vertex = [False] * n

    # 从每个未被访问过的节点开始进行深度优先搜索
    for node in range(n):
        if not visited[node]:
            dfs(graph, node, parent, visited, low, disc, is_cut_vertex, 0)
    
    # 返回割点的数量
    return sum(is_cut_vertex)

def main():
    # 读取输入
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u-1].append(v-1)
        graph[v-1].append(u-1)

    # 寻找割点的数量
    num_cut_vertices = find_cut_vertices(graph, n)

    # 根据割点的数量进行输出
    if num_cut_vertices == 0:
        print(1)
    else:
        print('Impossible')

if __name__ == '__main__':
    main()