题解 CF1209D 【Cow and Snacks】

2019-09-18 19:25:22


因为每只动物都有2个最喜欢的点心,所以以点心为点,连接所有动物喜欢的两种点心见图。

考虑一个大小 $>1$ 的联通块。肯定有一个动物得吃到2种点心,而总有一种排队顺序使得这个块中没有任何一头动物再吃到2种点心(比如说BFS序),那么一个大小为 $c$ 的联通块可以满足 $c-1$ 个动物。

设联通块个数为 $C$ ,则高兴的动物有 $n-C$ 个,悲伤的动物有 $m-(n-C)$ 个。

使用 $DSU$ (并查集)实现。

    #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;
    }