BFS求连通分量

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int ne[N],e[N],h[N],idx;
int n,m;
int ans;
bool st[550];
bool f[550];
void add(int a,int b)
{
    ne[idx] = h[a];
    e[idx] = b;
    h[a] = idx++;
}
void bfs(int x)
{
    queue<int> q;
    q.push(x);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = true;

        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(!st[j] && !f[j]) q.push(j),st[j] = true;
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while (m --)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }

    int k;
    cin >> k;
    for(int i = 0;i < n;i ++)
    {
        if(!st[i]) bfs(i),ans++;
    }
    int t = k;
    while (k --)
    {
        memset(st,false,sizeof st);
        int a,sum = 0;
        cin >> a;
        st[a] = true;
        f[a] = true;
        for (int i = 0;i < n;i ++)
        {
            if(!st[i] && !f[i]) bfs(i),sum ++;
        }
        if(sum <= ans) cout << "City " << a << " is lost." << endl;
        //如果去掉该城市后，连通分量变少了，说明该城市是一个单独的城市，不改变其他城市的联连通性
        if (sum > ans) cout << "Red Alert: City " << a << " is lost!" << endl;
        ans = sum;
    }
    if (t == n) cout << "Game Over." << endl;
    return 0;
}

并查集求连通分量