算法
(并查集)
对于每一对朋友关系,我们可以统计这两点的度数;对于每一对屏蔽关系,我们可以给这两点连一条无向边
然后利用每对朋友关系构造并查集
结论:
某个人的朋友候选人数 = 他所在连通分量的大小 - 自身 - 和他相邻的朋友人数 - 他所在连通分量中他屏蔽的人数
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int MX = 100005;
int deg[MX];
vector<int> to[MX];
int main() {
int n, m, k;
cin >> n >> m >> k;
dsu d(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
deg[a]++;
deg[b]++;
d.merge(a, b);
}
rep(i, k) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
rep(i, n) {
int ans = d.size(i) - 1 - deg[i];
for (int u : to[i]) {
ans -= d.same(i, u);
}
cout << ans << " ";
}
return 0;
}