题目链接
https://codeforces.com/gym/102769/problem/F
题意
n个人选若干个人，每有一个人友好值减一，每有俩个人是好朋友友好值加一，问最大友好值。
思路
题意转化成一个图中选取若干个点， 贡献等于这些点之间的边数减去点数。
不难发现，在一个非空的集合中，加入一个点永远不亏， 所以用并查集维护每个连通块的多余边数即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
int far[maxn], num[maxn];
int find(int x){
if(far[x] == x) return x;
else return far[x] = find(far[x]);
}
void unite(int x, int y){
x = find(x);
y = find(y);
if(x == y){
num[x]++;
return ;
}
far[x] = y;
num[y] += num[x];
}
void init(int n){
for(int i = 0;i <= n;i++){
num[i] = 0;
far[i] = i;
}
}
int main()
{
std::ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
int t;
cin >> t;
int cas = 0;
while(t--)
{
int n, m;
cin >> n >> m;
init(n);
for(int i = 0;i < m;i++){
int u, v;
cin >> u >> v;
unite(u, v);
}
set<int> st;
int ans = 0;
for(int i = 1;i <= n;i++) st.insert(find(i));
for(auto i : st) ans += max(0, num[i] - 1);
cout << "Case #" << ++cas << ": " << ans << endl;
}
return 0;
}