1 条题解

  • 0
    @ 2022-12-18 17:29:49
    #include <bits/stdc++.h>
    using namespace std;
    int n, m;
    int fa[2005];
    int cnt[2005];
    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 <= 2 * n; i++)
            fa[i] = i,
            cnt[i] = (i <= n); //1~n 是每个人所在的集合,1+n~n+n 是每个人的敌人所在的集合(抽象集合,初始人数为0)
        while (m--)
        {
            int p, u, v;
            cin >> p >> u >> v;
            if (p == 0)
            {
                int faU = findFa(u);
                int faV = findFa(v);
                if (faU != faV)
                {
                    fa[faU] = faV;
                    cnt[faV] += cnt[faU];
                }
            }
            else
            {
                int faU = findFa(u + n);
                int faV = findFa(v);
                if (faU != faV)
                {
                    fa[faU] = faV;
                    cnt[faV] += cnt[faU];
                }
                faU = findFa(u);
                faV = findFa(v + n);
                if (faU != faV)
                {
                    fa[faU] = faV;
                    cnt[faV] += cnt[faU];
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= 2 * n; i++)
            if (fa[i] == i && cnt[i] > 0)
                ans++;
        cout << ans << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    614
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    (无)
    递交数
    48
    已通过
    25
    上传者