AcWing 1485. 战争中的城市
原题链接
中等
作者:
王小强
,
2021-02-23 18:40:13
,
阅读 22
算法1: DFS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k, u, v;
void dfs(vector<vector<int>>& g, vector<int>& seen, int cur) {
if (seen[cur]++) return;
for (const auto& nxt : g[cur]) dfs(g, seen, nxt);
}
int main(void) {
scanf("%d %d %d", &n, &m, &k);
vector<vector<int>> graph(n + 1);
// build the undirected graph!
while (m--) {
scanf("%d %d", &u, &v);
graph[u].emplace_back(v);
graph[v].emplace_back(u);
}
vector<int> cities(k);
for (int i = 0; i < k; ++i) cin >> cities[i];
// reconstruct the graph (delete a city)
for (const auto& city : cities) {
vector<vector<int>> g(graph); // clone
for (const int nei : g[city])
g[nei].erase(find(begin(g[nei]), end(g[nei]), city));
g[city].clear();
int ccs = 0; // the number of the connected components!!!
vector<int> seen(n + 1);
for (int i = 1; i <= n; ++i) {
if (i == city || seen[i]) continue;
dfs(g, seen, i);
++ccs;
}
printf("%d\n", ccs - 1);
}
}
TODO: 算法2: Disjoint Set!