相亲数据匹配

E相亲数据匹配

通过读题可知，本题就是求在同一个图内的两种点的数量。

如果查询的点的属性是0，那就是求同一张图内属性为1的点的数量。

做法有很多种，出题人的STD是并查集，因为并查集好写（好拉板子）。

并查集过程中记录同一张图内两种点的数量即可。

//
// Created by td1336065617 on 2024/7/31.
//
#include <bits/stdc++.h>
using namespace std;
int bcj[110000], bcjsum[110000][2], xingbie[110000];
int n, m;
int find_bcj(int fx) {
    return bcj[fx] == fx ? fx : bcj[fx] = find_bcj(bcj[fx]);
}
int main() {
   // freopen("01/10.in", " r ", stdin);
   // freopen("01/10.out", " w ", stdout);

    cin >> n >> m;
    if (n < 1 || n>100000) {
        return -1;
    }
    if (m < 1 || m>100000) {
        return -2;
    }
    for (int i = 1; i <= n; i++)
    {
        bcj[i] = i;
        int xb;
        cin >> xb;
        if (xb < 0 || xb>1) {
            return -3;
        }
        xingbie[i]=xb;
        bcjsum[i][xb]++;
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x < 1 || x>n) {
            return -4;
        }
        if (y < 1 || y>n) {
            return -5;
        }
        if (x==y) {
            return -6;
        }
        int fx = find_bcj(x), fy = find_bcj(y);
        if (fx != fy) {
            bcj[fy] = fx;
            bcjsum[fx][1] += bcjsum[fy][1];
            bcjsum[fx][0] += bcjsum[fy][0];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << bcjsum[find_bcj(i)][!xingbie[i]] << endl;
    }
    return 0;
}