阳光大学封锁问题 - 最少河蟹数量 - 常规

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

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

阳光大学的校园是一张由 $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）来解决。

首先，我们需要构建图的邻接表表示，用一个vector<vector>来存储每个节点的邻居节点。

然后，我们可以使用DFS遍历图，对于每个节点，我们都可以选择封锁或者不封锁。如果选择封锁当前节点，则需要将与当前节点相连的道路都封锁。如果选择不封锁当前节点，则需要继续DFS遍历当前节点的所有邻居节点。

在DFS过程中，我们使用一个visited数组来记录每个节点是否已经被访问过。如果某个节点已经被访问过，则说明在DFS过程中会形成环，即两只河蟹会发生冲突。因此，我们可以在DFS的过程中，通过判断visited数组来避免发生冲突。

最后，我们统计封锁的节点数，并输出结果。

算法步骤

构建图的邻接表表示。
定义一个visited数组，用来记录每个节点是否已经被访问过。
定义一个count变量，用来统计封锁的节点数。
使用DFS遍历图的每个节点：
- 如果当前节点已经被访问过，则直接跳过。
- 封锁当前节点，并递归DFS遍历当前节点的所有邻居节点。
- 统计封锁的节点数。
输出结果。

代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    graph.resize(n + 1);
    visited.resize(n + 1, false);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    int count = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }
    
    if (count == 1) {
        cout << "0" << endl;
    } else {
        cout << "Impossible" << endl;
    }
    
    return 0;
}

复杂度分析

该算法的时间复杂度为O(n + m)，其中n为节点数，m为边数。在DFS过程中，每个节点和每条边都会被访问一次。

空间复杂度为O(n)，需要额外的空间来存储图的邻接表和visited数组。