L2-013 红色警报 分数 25

时间复杂度 N*M≈2.5e6

#include <bits/stdc++.h>
using namespace std;
int n = 510, m;
const int N = 510;
vector<pair<int,int>> path;    // 储存所有边
int p[N];    // 储存祖宗节点
bool flag[N];    // 判断是否已经被去除
void init()    // 初始化所有祖宗节点
{
    for(int i = 0; i < n; ++ i)
        p[i] = i;
}
int find(int x)    // find函数（包含路径压缩）
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void minimerge(int a, int b)    // 合并
{
    int fa = find(a), fb = find(b);
    if(fa != fb) p[fa] = fb;
}
void merge()    // 合并函数（注意：如果一条边的两个顶点均未被删除才添加）
{
    for(auto pi : path)
    {
        if(flag[pi.first] == false && flag[pi.second] == false)
            minimerge(pi.first, pi.second);
    }
}
int fenzhi()    // 循环判断有多少分支
{
    int cnt = 0;
    for(int i = 0; i < n; ++ i)
        if(p[i] == i && flag[i] == false) ++ cnt;
    return cnt;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int a, b;
        scanf("%d%d",&a,&b);
        path.push_back({a,b});
    }
    init();
    merge();
    int k;
    cin >> k;
    for(int i = 1; i <= k; ++ i)
    {
        int now = fenzhi();
        int dis;
        scanf("%d",&dis);
        flag[dis] = true;
        init();
        merge();
        int next = fenzhi();
        // 当且仅当连通分支数减少时，发出警报
        if(now < next) cout << "Red Alert: ";
        cout << "City " << dis << " is lost" << ".!"[now<next] << "\n";
    }
    if(k == n) printf("Game Over.\n");
    return 0;
}