GPLT L2-013. 红色警报 判连通度

本来只是一个直接求连通度的问题,但是题说:＂注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。 ＂

这个地方怎么绕..方法是删掉边之后不要去除该城市，一样把被攻占的点放在连通度里考虑，这样做能够忽略那些孤立点带来的影响(即切除一个孤立点的边不影响连通度)．

若删除后，把一个连通块分成２部分，实际上这个块的连通度由１变成了３．若只是变成了２，说明切出来了一个孤立点，实际连通度不变．比如(A)----(B),切去(A)，连通度仍为１(算上Ａ为２，即切除前后连通度差不够２)．

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
const int inf = 0x3f3f3f3f, maxN = 505;
int N, M;
int G[maxN][maxN], vis[maxN];

void dfs(int s) {
    vis[s] = 1;
    rep(i, 0, N)
        if (G[s][i] && !vis[i])
            dfs(i);
}
int city() {
    int cnt = 0;
    mst(vis, 0);
    rep(i, 0, N) {
        if (!vis[i]) {
            ++cnt;
            dfs(i);
        }
    }
    return cnt;
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d %d", &N, &M);
    int a, b;
    mst(G, 0);
    rep(i, 0, M) {
        scanf("%d %d", &a, &b);
        G[a][b] = G[b][a] = 1;
    }
    int T, lo, before, after;
    before = city();

    scanf("%d", &T);
    rep(i, 0, T) {
        scanf("%d", &lo);
        rep(j, 0, N)
            G[j][lo] = G[lo][j] = 0;
        after = city();
        if (after > before + 1)
            printf("Red Alert: City %d is lost!\n", lo);
        else
            printf("City %d is lost.\n", lo);
        before = after;

        if (i == N - 1) {
            printf("Game Over.");
        }
    }
    return 0;
}