D. Cow and Snacks
參考:Codeforces 1209D. Cow and Snacks
思路:利用并查集,建構一個生成樹,然後樹的邊數就是能夠開心的客人的人數。用一個條件
find(u)!=find(v)
(我在代碼裡反了一下),來統計某一種味道的菜是否已經被吃掉,如果等于,則證明已經被吃掉。
另外:
函數一定要記得記憶化,不然很容易逾時
find()
代碼:
// Created by CAD on 2019/9/18.
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int fa[maxn];
inline int find(int x)
{
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy) fa[fx]=fy;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m; cin>>n>>m;
for(int i=1;i<=n;++i) fa[i]=i;
int u,v,ans=0;
for(int i=1;i<=m;++i)
{
cin>>u>>v;
if(find(u)==find(v)) ans++;
merge(u,v);
}
cout<<ans<<endl;
return 0;
}