题解 CF1209D 【Cow and Snacks】
SIGSEGV
2019-09-18 19:25:22
因为每只动物都有2个最喜欢的点心，所以以点心为点，连接所有动物喜欢的两种点心见图。
考虑一个大小$>1$的联通块。肯定有一个动物得吃到2种点心，而总有一种排队顺序使得这个块中没有任何一头动物再吃到2种点心（比如说BFS序），那么一个大小为$c$的联通块可以满足$c-1$个动物。
设联通块个数为$C$，则高兴的动物有$n-C$个，悲伤的动物有$m-(n-C)$个。
使用$DSU$（并查集）实现。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,kk,f[N],sz[N];
int getf(int v) {if (f[v] != v) f[v] = getf(f[v]);return f[v];}
int main ()
{
ios::sync_with_stdio(false);
cin >> n >> kk;
int t1,t2;
for (int i = 1;i <= n;i++) f[i] = i;
for (int i = 1;i <= kk;i++)
{
cin >> t1 >> t2;
f[getf(t1)] = getf(t2);
}
int cnt = 0;
for (int i = 1;i <= n;i++) if (f[i] == i) ++cnt;
cout << kk - (n - cnt);
return 0;
}
```