摘要
Title: L2-013 红色警报 (25 分)
Tag: DFS、连通块
Memory Limit: 64 MB
Time Limit: 1000 ms

L2-013 红色警报 (25 分)

题意

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
思路

DFS找连通块即可，如果被攻占，意味着之前已经被标记了，统计攻占前和攻占后的连通块数即可
复杂度 $O(nkm)$

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-21 10:16:41
* @FilePath: \ACM\GPLT\L2-013.CPP
* @LastEditTime: 2022-04-21 10:29:52
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 510;
vector<int> g[N];
int n, m, k, st[N];

void dfs(int u, int fa)
{
    for (auto v : g[u])
    {
        if (fa == v || st[v])
            continue;
        st[v] = 1;
        dfs(v, u);
    }
}

signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> k;
    vector<int> vis;
    for (int i = 1; i <= k; ++i)
    {
        int x, cnt1 = 0, cnt2 = 0;
        cin >> x;

        memset(st, 0, sizeof st);
        for (auto u : vis)
            st[u] = 1;
        for (int i = 0; i < n; ++i)
        {
            if (!st[i])
            {
                dfs(i, -1);
                cnt1 += 1;
            }
        }

        vis.push_back(x);

        memset(st, 0, sizeof st);
        for (auto u : vis)
            st[u] = 1;
        for (int i = 0; i < n; ++i)
        {
            if (!st[i])
            {
                dfs(i, -1);
                cnt2 += 1;
            }
        }
        if (cnt2 > cnt1)
            printf("Red Alert: City %lld is lost!\n", x);
        else
            printf("City %lld is lost.\n", x);
    }
    if (n == k)
        printf("Game Over.");
    return 0;
}

L2-013 红色警报 (25 分)

题意

思路

代码