CF1209D Cow and Snacks 题解

题目链接：CF1209D Cow and Snacks

题意：

\(n\) 种小吃，\(k\) 个客人，每个人喜欢两种编号不同的小吃。但是每种小吃在小吃店里只有一坨。

客人按顺序进入小吃店，会买走所有她喜欢且仍在店铺里的小吃。如果一个客人买不到任何一束小吃，那么她就会十分沮丧导致变成肥宅。现在你可以自己安排这 \(k\) 个人的顺序，使得肥宅的数量最小。

注意，只拿到一种小吃的客人不会变成肥宅。

输入格式：

The first line contains integers \(n\) and \(k\) ( \(2 \le n \le 10^5\) , \(1 \le k \le 10^5\) ), the number of snacks and the number of guests.

The $ i $ -th of the following \(k\) lines contains two integers \(x_i\) and \(y_i\) ( \(1 \le x_i, y_i \le n\) , \(x_i \ne y_i\) ), favorite snack flavors of the $ i $ -th guest.

输出格式：

Output one integer, the smallest possible number of sad guests.

如果客人 \(i\) 喜欢吃 \(u_i,v_i\) ，则我们将 \(u_i,v_i\) 连一条无向边。

考虑并查集维护。如果合并成功，则肥宅数量减少 \(1\) 。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,k,res,f[N],sz[N];
void init(int n) { for(int i=1; i<=n; i++) f[i] = i, sz[i] = 1; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return 0;
    if(sz[x] > sz[y]) swap(x,y);
    f[x] = y; sz[y] += sz[x]; return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; init(n);
    for(int i=1,u,v; i<=k; i++)
    { cin >> u >> v; res += merge(u,v); }
    cout << k - res << '\n';
    return 0;
}