题目链接：https://codeforces.com/contest/1209/problem/D
赛后补题（事实证明思维很重要）
题意：输入n和m，表示有n种食物（编号从1到n）和m个人，每一个人都会有两种喜欢吃的食物，接下来m行，每行两个数字，表示第i个人喜欢吃的两种食物的编号，当轮到一个人吃的时候，他就会把他喜欢吃的两种食物都吃完，假如某个人喜欢吃的两种食物都没有了（被别人吃完了），只吃一种他是不会哭的，只有两种都吃完了他才会哭，现在问你按照一定的顺序让他们吃东西，最少有几个人会哭。
思路：把人当做边，食物当做这条边两头的节点，这样建图（实际上也不用建，就直接集合合并就行了）之后我们用并查集求一下有几个连通块（假设数量是num），
答案就是m-（n-num）。我们这样想，一个人如果吃了两种食物，那么我们认为他“浪费”了一份食物，对于num个集合，每一个集合一定有一个人会吃两种食物（对于集合中只有一个节点的特殊情况，这个食物没人吃，也是算“浪费”的），那么就有num份食物被浪费了，这样算的话就有n-num种食物是没有被“浪费”的，实际上就是分别被一个人吃了，所以就有n-num个人是不会哭的，最后当然就有m-（n-num）个人会哭了
代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 200005 int pre[maxn],n,m,k,t; void init(){ for(int i=1;i<=n;i++) pre[i]=i; } int find(int x){ return pre[x]==x?x:pre[x]=find(pre[x]); } int main() { while(cin>>n>>m){ init(); int u,v; for(int i=1;i<=m;i++){ cin>>u>>v; int x=find(u); int y=find(v); if(x!=y){ pre[x]=y; } } int num=0; for(int i=1;i<=n;i++){ if(find(i)==i) num++;//每增加一个并查集就代表一个食物被'浪费'了 } int ans=m-(n-num); cout<<ans<<endl; } return 0; }