星球大战

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
struct Edge
{
    int u, v;
};
Edge e[200005];
vector<int> ee[400005];
bool flag[400005]; //是否被打击了
int q[400005];
int ans[400005];
int fa[400005];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        cin >> e[i].u >> e[i].v;
        ee[e[i].u].push_back(e[i].v);
        ee[e[i].v].push_back(e[i].u);
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> q[i];
        flag[q[i]] = true;
    }
    int cnt = n - k;
    for (int i = 1; i <= m; i++)
    {
        if (!flag[e[i].u] && !flag[e[i].v])
        {
            int fa1 = findFa(e[i].u);
            int fa2 = findFa(e[i].v);
            if (fa1 != fa2)
            {
                cnt--;
                fa[fa1] = fa2;
            }
        }
    }
    for (int i = k; i >= 1; i--)
    {
        int u = q[i];
        ans[i] = cnt;
        cnt++;
        flag[u] = false;
        for (int j = 0; j < ee[u].size(); j++)
        {
            int v = ee[u][j];
            if (flag[v])
                continue;
            int fa1 = findFa(u);
            int fa2 = findFa(v);
            if (fa1 != fa2)
            {
                cnt--;
                fa[fa1] = fa2;
            }
        }
    }
    cout << cnt << "\n";
    for (int i = 1; i <= k; i++)
        cout << ans[i] << "\n";
    return 0;
}

村村通

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int fa[1005];
int findF(int x)
{
    if (fa[x] == x)
        return x;
    else
        return fa[x] = findF(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n && n != 0)
    {
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        cin >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            int fu = findF(u);
            int fv = findF(v);
            if (fu != fv)
                fa[fu] = fv;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (fa[i] == i)
                ans++;
        cout << ans - 1 << endl;
    }
    return 0;
}

程序自动分析

离散化

#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int x[112345], y[112345], e[112345];
vector<int> a;//离散化
int fa[212345];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--)
    {
        a.clear();//离散化
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> x[i] >> y[i] >> e[i];
            a.push_back(x[i]);//离散化
            a.push_back(y[i]);//离散化
        }
        sort(a.begin(), a.end());//离散化
        for (int i = 1; i <= n; i++)
        {
            x[i] = lower_bound(a.begin(), a.end(), x[i]) - a.begin();//离散化
            y[i] = lower_bound(a.begin(), a.end(), y[i]) - a.begin();//离散化
        }
        for (int i = 0; i < a.size(); i++)
            fa[i] = i;
        for (int i = 1; i <= n; i++)
        {
            if (e[i] == 1)
            {
                int fx = findFa(x[i]);
                int fy = findFa(y[i]);
                fa[fx] = fy;
            }
        }
        bool flag = true;
        for (int i = 1; i <= n; i++)
        {
            if (e[i] == 0)
            {
                int fx = findFa(x[i]);
                int fy = findFa(y[i]);
                if (fx == fy)
                {
                    flag = false;
                    break;
                }
            }
        }
        cout << (flag ? "YES\n" : "NO\n");
    }
    return 0;
}