首页 > 代码库 > PAT 1013 Battle Over Cities
PAT 1013 Battle Over Cities
#include <cstdio>#include <cstdlib>#include <vector>using namespace std;class City {public: vector<int> adj; bool visited; City() : visited(false) {}};void dfs(int idx, vector<City>& cities) { if (cities[idx].visited) { return; } City& city = cities[idx]; city.visited = true; for (int i=0; i<city.adj.size(); i++) { dfs(city.adj[i], cities); }}void reset_cities(vector<City>& cities) { int len = cities.size(); for (int i=0; i<len; i++) { cities[i].visited = false; }}int main() { int N = 0, M = 0, K = 0; scanf("%d%d%d", &N, &M, &K); vector<City> cities(N + 1); for (int i=0; i<M; i++) { int a, b; scanf("%d%d", &a, &b); cities[a].adj.push_back(b); cities[b].adj.push_back(a); } for (int i=0; i<K; i++) { int parts = 0; reset_cities(cities); int oc = -1; scanf("%d", &oc); cities[oc].visited = true; for (int i=1; i<=N; i++) { if (cities[i].visited) continue; parts++; dfs(i, cities); } printf("%d\n", parts - 1); } return 0;}
通过dfs把可以联通的区域的节点设置为visited=true,这样对visited=false的节点进行了几次dfs就有几个不相连的区域,除去一个被占领的city,剩下的就是需要重新连接起来的区域,区域个数-1就是需要修复的路的数量
PAT 1013 Battle Over Cities
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。