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;

}

巴特西

Cow and Snacks

最新文章

热门文章