AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 1485. 战争中的城市    原题链接    中等

作者: 作者的头像   王小强 ,  2021-02-23 18:40:13 ,  阅读 22


1


算法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!

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息