封锁阳光大学/n/n## 题目描述/n/n曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。/n/n阳光大学的校园是一张由 $n$ 个点构成的无向图，$n$ 个点之间由 $m$ 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。/n/n询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。/n/n## 输入格式/n/n第一行两个正整数，表示节点数和边数。/n接下来 $m$ 行，每行两个整数 $u,v$，表示点 $u$ 到点 $v$ 之间有道路相连。/n/n## 输出格式/n/n仅一行如果河蟹无法封锁所有道路，则输出 'Impossible'，否则输出一个整数，表示最少需要多少只河蟹。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n3 3/n1 2/n1 3/n2 3/n/n/n### 样例输出 #1/n/n/nImpossible/n/n/n## 样例 #2/n/n### 样例输入 #2/n/n/n3 2/n1 2/n2 3/n/n/n### 样例输出 #2/n/n/n1/n/n/n## 提示/n/n【数据规模】 /n对于 $100/%$ 的数据，$1/le n /le 10^4$，$1/le m /le 10^5$，保证没有重边。/n/n### 解法一：并查集/n/n首先我们可以使用并查集来解决这个问题。并查集可以用来维护节点之间的连通性。/n/n我们可以将节点看作是并查集中的元素，道路看作是并查集中的连接。我们需要将所有的道路连接起来，并查集中的每个元素都是一个连通分量。/n/n首先，我们初始化并查集，将每个节点都初始化为一个独立的连通分量。/n/n然后，我们遍历所有的道路，将每个道路的两个节点进行合并。如果两个节点已经属于同一个连通分量，那么它们之间的道路就是多余的，我们可以将这条道路删去。/n/n最后，我们统计并查集中的连通分量的数量。如果连通分量的数量大于1，说明存在无法封锁的道路，输出 'Impossible'；否则，输出连通分量的数量减1，即为最少需要的河蟹的数量。/n/ncpp/n#include <iostream>/n#include <vector>/n/nusing namespace std;/n/nclass UnionFind {/nprivate:/n vector<int> parent;/n vector<int> rank;/npublic:/n UnionFind(int n) {/n parent.resize(n + 1);/n rank.resize(n + 1);/n for (int i = 1; i <= n; i++) {/n parent[i] = i;/n rank[i] = 0;/n }/n }/n/n int find(int x) {/n if (x != parent[x]) {/n parent[x] = find(parent[x]);/n }/n return parent[x];/n }/n/n void unite(int x, int y) {/n x = find(x);/n y = find(y);/n if (x == y) {/n return;/n }/n if (rank[x] < rank[y]) {/n parent[x] = y;/n } else {/n parent[y] = x;/n if (rank[x] == rank[y]) {/n rank[x]++;/n }/n }/n }/n};/n/nint main() {/n int n, m;/n cin >> n >> m;/n UnionFind uf(n);/n vector<pair<int, int>> roads(m);/n for (int i = 0; i < m; i++) {/n cin >> roads[i].first >> roads[i].second;/n }/n for (int i = 0; i < m; i++) {/n int x = roads[i].first;/n int y = roads[i].second;/n uf.unite(x, y);/n }/n int cnt = 0;/n for (int i = 1; i <= n; i++) {/n if (uf.find(i) == i) {/n cnt++;/n }/n }/n if (cnt > 1) {/n cout << /'Impossible/' << endl;/n } else {/n cout << cnt - 1 << endl;/n }/n return 0;/n}/n/n/n### 解法二：拓扑排序/n/n我们还可以使用拓扑排序来解决这个问题。/n/n我们可以将每个节点看作是一个任务，道路看作是任务之间的依赖关系。我们需要按照依赖关系的顺序来完成任务。/n/n首先，我们计算每个节点的入度，即有多少个节点依赖于该节点。根据道路的连接关系，我们可以将入度为0的节点加入到一个队列中。/n/n然后，我们从队列中依次取出节点，并将与该节点相连的节点的入度减1。如果减1后的节点入度为0，则将该节点加入到队列中。重复上述过程，直到队列为空。/n/n最后，我们统计完成的任务的数量。如果完成的任务的数量小于节点的数量，说明存在无法封锁的道路，输出 'Impossible'；否则，输出完成的任务的数量减1，即为最少需要的河蟹的数量。/n/ncpp/n#include <iostream>/n#include <vector>/n#include <queue>/n/nusing namespace std;/n/nint main() {/n int n, m;/n cin >> n >> m;/n vector<int> indegree(n + 1, 0);/n vector<vector<int>> adj(n + 1);/n for (int i = 0; i < m; i++) {/n int u, v;/n cin >> u >> v;/n indegree[v]++;/n adj[u].push_back(v);/n }/n queue<int> q;/n for (int i = 1; i <= n; i++) {/n if (indegree[i] == 0) {/n q.push(i);/n }/n }/n int cnt = 0;/n while (!q.empty()) {/n int u = q.front();/n q.pop();/n cnt++;/n for (int v : adj[u]) {/n indegree[v]--;/n if (indegree[v] == 0) {/n q.push(v);/n }/n }/n }/n if (cnt < n) {/n cout << /'Impossible/' << endl;/n } else {/n cout << cnt - 1 << endl;/n }/n return 0;/n}/n/n/n### 复杂度分析/n/n无论是使用并查集还是拓扑排序，都需要遍历所有的道路，时间复杂度为 $O(m)$。并查集的时间复杂度为 $O(//alpha(n))$，其中 $//alpha(n)$ 是反阿克曼函数的某个非常小的值，可以看作是常数。拓扑排序的时间复杂度为 $O(n)$。因此，总的时间复杂度为 $O(m)$。/n/n空间复杂度为 $O(n)$，其中 $n$ 是节点的数量。/n