L2-013 红色警报

思路1

• dfs 解决连通块问题

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e3 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f3f3f3f;
int g[N][N];
int n, m;
int st[N];
// 访问以u为跟的连通块，并且都设为已经访问
void dfs(int u)
{
    for(int i = 0; i < n; i ++)
    {
        if(st[i]  == 0&& g[u][i] == 1)
        {
            st[i] = 1;
            dfs(i);
        }
    }
}
int get_sum()
{
    int cnt = 0;
    // 计算当前联通块的个数
    for(int i = 0; i < n; i ++)
    {
        if(st[i] == 0)
        {
            dfs(i);
            cnt ++;
        }
    }
    return cnt;
}
signed main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = g[y][x] = 1;
    }
    int oldx = get_sum();
    int t;
    cin >> t;
    for(int i = 0; i < t; i ++)
    {
        int id;
        cin >> id;
        for(int i = 0; i < n; i ++)
        {
            g[id][i] = 0;
            g[i][id] = 0;
        }
        memset(st, 0, sizeof st);
        int newx = get_sum();
        //cout << oldx << ' ' <<newx <<endl;
        if(newx - oldx <= 1) printf("City %d is lost.\n", id);
        else if(newx - oldx > 1)
        {
            printf("Red Alert: City %d is lost!\n", id);
        }
        oldx = newx;
    }
    if(t == n) cout << "Game Over." << endl;
    return 0;
}

思路2

• 并查集解决连通块问题

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 5e3 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct node
{
    int x, y;
    int flag;
}edge[N];
int p[N];
int find_fa(int x)
{
    if(x != p[x]) p[x] = find_fa(p[x]);
    return p[x];
}
void Merge(int x, int y)
{
    int fax = find_fa(x), fay = find_fa(y);
    if(fax != fay)
    {
        p[fax] = fay;
    }
}
int n, m;
signed main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) p[i] = i;
    for(int i = 0; i < m; i ++)
    {
        cin >> edge[i].x >> edge[i].y;
        edge[i].flag = 0;
        Merge(edge[i].x, edge[i].y);
    }
    int oldcnt = 0, newcnt = 0;
    for(int i = 0; i < n; i ++)
    {
        //cout <<"hehe: " <<find_fa(i) << endl;
        if(find_fa(i) == i) oldcnt ++;
    }
    //cout << oldcnt  <<endl;
    int t;
    cin >> t;
    for(int i = 0; i < t; i ++)
    {

        int id;
        cin >> id;
        // 删除城市的连通点
        for(int j = 0; j < m; j ++)
        {
            if(edge[j].x == id || edge[j].y == id)
            {
                edge[j].flag = 1;
            }
        }
        for(int i = 0; i < n; i ++) p[i] = i;

        for(int j = 0; j < m; j ++)
        {
            if(edge[j].flag == 0)
            {
                Merge(edge[j].x, edge[j].y);
            }
        }

        for(int i = 0; i < n; i ++)
        {
            //cout << "i : " << i  << find_fa(i) << endl;
            if(i == find_fa(i)) newcnt ++;
        }
        //cout << oldcnt << ' ' <<newcnt <<endl;
        if(newcnt - oldcnt > 1)
        {
            printf("Red Alert: City %d is lost!\n", id);
        }
        else printf("City %d is lost.\n", id);

        oldcnt = newcnt;
        newcnt = 0;
    }
    if(t == n) cout << "Game Over." << endl;
    return 0;
}