被黄题创死了2333
首先肯定有一个贪心的想法：尽量使得人们拿的花重复，即尽量使得每个人都拿一束花。当然第一个人必须拿两束。
接着思考：如何找出有几个人是必须拿两束花的。
其实很简单，当 \(A,B\) 两人不能通过其他人使得他们的花有联系，比如 \(A\) 喜欢 \(1,2\)，\(B\) 喜欢 \(3,4\)，那么由于两个人一点联系也没有，所以只能两人都取两束。
但如果还有一人 \(C\) 喜欢 \(2,3\)，那么 \(A,B,C\) 就是联系起来的，可以按照 \(A,C,B\) 的顺序取。
那么本质上我们需要描述集合关系，也就是要先判断哪些人的花束会存在联系。这使用并查集就行。
对于一个大小为 \(x\) 的花束集合，一定存在一种顺序，使得第一个人取 \(2\) 束，剩下的人取 \(1\) 束，所以最多容纳 \(x-1\) 个人。
找出所有的集合大小，答案就是 \(k-\sum (x-1)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int fa[N],siz[N];
int find(int x) {
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int main() {
cin>>n>>k;
for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
for(int i=1;i<=k;i++) {
int x,y; cin>>x>>y;
int fx=find(x),fy=find(y);
if(fx!=fy) {
fa[fx]=fy;
siz[fy]+=siz[fx];
}
}
int sum=0;
for(int i=1;i<=n;i++) {
if(fa[i]==i) sum+=siz[i]-1;
}
cout<<k-sum;
return 0;
}