输入样例

5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3

输出样例

City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;

const int N = 510, M = 5010;
int n, m, k;
int p[N];
PII cnt[M];
bool st[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;

    int sum = 0;
    for (int i = 0; i < n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cnt[i] = { a,b };
        if (find(a) != find(b)) p[find(a)] = find(b);
    }

    for (int i = 0; i < n; i++)
        if (p[i] == i) sum++;

    cin >> k;
    for (int i = 0; i < k; i++) {
        int a;
        cin >> a;
        st[a] = true;
        int cur = 0;
        for (int j = 0; j < n; j++) p[j] = j;
        for (int j = 0; j < m; j++) {
            int a = cnt[j].x, b = cnt[j].y;
            if (st[a] || st[b]) continue;
            if (find(a) != find(b)) p[find(a)] = find(b);
        }
        for (int j = 0; j < n; j++)
            if (p[j] == j) cur++;

        //sum==cur：删除的结点是孤立的结点，删除前后集合数量不变
        //sum==cur：删除的结点是叶子结点，删除前后集合数量加1
        if (sum == cur || sum == cur - 1) printf("City %d is lost.\n", a);
        else printf("Red Alert: City %d is lost!\n", a);
        //只要删除的不是孤立结点和叶节点就会改变连通性
        //即使原图本身已经不连通，但依旧会破坏连通子图的连通性
        sum = cur;
    }

    if (k == n) cout << "Game Over." << endl;

    return 0;
}