封锁阳光大学 - 图论问题解题思路及代码实现

题目描述

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

Impossible

样例 #2

样例输入 #2

3 2
1 2
2 3

样例输出 #2

提示

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

解题思路

这是一个经典的图论问题，可以使用深度优先搜索（DFS）来解决。

首先，我们需要构建图的邻接表表示。然后，我们从任意一个未被访问过的节点开始进行DFS，每次DFS访问到一个节点时，将该节点标记为已访问，并将与该节点相邻的未被访问过的节点加入到DFS的递归调用中。

在DFS的递归调用中，我们需要记录每个节点的状态，有三种状态：

未被访问过的节点：状态为0；
正在被DFS访问过的节点：状态为1；
已经被DFS访问过的节点：状态为2。

在DFS的递归调用中，我们需要判断当前节点的状态：

如果当前节点的状态为1，说明当前节点正在被DFS访问过，即存在环路，直接返回 'Impossible'；
如果当前节点的状态为2，说明当前节点已经被DFS访问过，直接返回；
如果当前节点的状态为0，说明当前节点未被访问过，将其状态设置为1，并继续DFS访问与当前节点相邻的节点。

如果DFS递归调用结束后，没有返回 'Impossible'，则说明可以封锁所有道路，返回0。

代码实现

# 邻接表表示图
adjacency_list = {}

# 节点状态
node_status = {}

# DFS函数
def dfs(node):
    # 当前节点状态为1，说明存在环路
    if node_status[node] == 1:
        return 'Impossible'
    # 当前节点状态为2，说明已经被访问过
    if node_status[node] == 2:
        return
    # 当前节点状态为0，说明未被访问过
    node_status[node] = 1
    # 遍历当前节点的邻居节点
    for neighbor in adjacency_list[node]:
        # 递归调用DFS
        dfs(neighbor)
    # 当前节点已经被访问过
    node_status[node] = 2

# 主函数
def main():
    # 读取输入
    n, m = map(int, input().split())
    # 初始化邻接表
    for i in range(1, n + 1):
        adjacency_list[i] = []
    # 初始化节点状态
    for i in range(1, n + 1):
        node_status[i] = 0
    # 读取边
    for _ in range(m):
        u, v = map(int, input().split())
        adjacency_list[u].append(v)
        adjacency_list[v].append(u)
    # 从任意一个节点开始DFS
    dfs(1)
    # 如果没有返回'Impossible'，说明可以封锁所有道路
    if 'Impossible' not in node_status.values():
        print(0)
    else:
        print('Impossible')

# 执行主函数
if __name__ == '__main__':
    main()