本文共 2390 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要编写一个报警程序，判断当一个城市被攻占后是否会导致国家连通性被破坏。如果破坏连通性，则发出红色警报；否则，只输出普通信息。最后，如果所有城市都被攻占，输出“Game Over”。

方法思路

解决代码

#include 
   
    
using namespace std;
#define INF 0x3F3F3F3F
#define pb push_back
const int N = 500 + 1;
const int MOD = 1e9 + 7;
int par[N], rnk[N];
void init(int n) {
    for (int i = 0; i < n; ++i) {
        par[i] = i;
        rnk[i] = 1;
    }
}
int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rnk[y] == rnk[x]) rnk[x]++;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        unite(x, y);
    }
    vector
    
     
      > roads(m);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        roads[i] = make_pair(x, y);
    }
    int k;
    cin >> k;
    vector
      
        lostCities;
    for (int i = 0; i < k; ++i) {
        int x;
        cin >> x;
        lostCities.push_back(x);
    }
    bool lost[N] = false;
    for (int x : lostCities) {
        lost[x] = true;
        int cnt0 = 0;
        for (int i = 0; i < n; ++i) {
            if (par[i] == i) cnt0++;
        }
        for (int i = 0; i < m; ++i) {
            int u = roads[i].first;
            int v = roads[i].second;
            if (!lost[u] && !lost[v]) {
                unite(u, v);
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (par[i] == i) cnt++;
        }
        if (cnt > cnt0) {
            cout << "Red Alert: City " << x << " is lost!" << endl;
        } else {
            cout << "City " << x << " is lost." << endl;
        }
        if (lost[n-1]) {
            cout << "Game Over." << endl;
        }
    }
    return 0;
}
      
     
    
   

代码解释

转载地址：http://liwzz.baihongyu.com/