阳光大学封锁问题：最少河蟹数量算法

阳光大学封锁问题：最少河蟹数量算法

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

阳光大学的校园是一张由 $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$，保证没有重边。

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

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> graph(n+1);
    vector<int> indegree(n+1, 0);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        
        graph[u].push_back(v);
        graph[v].push_back(u);
        indegree[u]++;
        indegree[v]++;
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 1) {
            q.push(i);
        }
    }
    
    int count = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        if (indegree[node] != 1) {
            continue;
        }
        
        count++;
        
        for (int i = 0; i < graph[node].size(); i++) {
            int neighbor = graph[node][i];
            indegree[neighbor]--;
            
            if (indegree[neighbor] == 1) {
                q.push(neighbor);
            }
        }
    }
    
    if (count == n) {
        cout << 1 << endl;
    } else {
        cout << "Impossible" << endl;
    }
    
    return 0;
}