codeforces1209——D.Cow and Snacks（并查集）-阿里云开发者社区

codeforces1209——D.Cow and Snacks（并查集）

2022-11-30 83

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： codeforces1209——D.Cow and Snacks（并查集）

原题链接

题意：

n种食物，一种食物只有一个，m个人，每个人有两种喜欢吃的食物。每个人来的时候会把喜欢吃的未被吃过的食物都吃掉，如果吃不到食物的话就会难过，适当安排序列，使得难过的人最少，并输出该数量。

思路：

读错题了，以为是匹配。本题中人可能不止吃一个食物。

考虑把食物看成节点，第一个来的人肯定是吃两个食物，这就构成了一条边。以后每来一个人，如果两个喜欢的食物在一个连通块里的话，说明都被以前的人吃了，他就会不开心；否则，就一定会有食物吃。

用并查集维护就好了。

代码：

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+100,N=1e6+100;
const double PI = atan(1.0)*4;
const double eps=1e-6;
int root[maxn],cnt=0,n,m;
int Find(int x){
    if(x!=root[x]) root[x]=Find(root[x]);
    return root[x];
}
void Union(int u,int v){
    u=Find(u),v=Find(v);
    if(u!=v){
        cnt++;
        root[u]=v;
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) root[i]=i;
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        Union(u,v);
    }
    out(m-cnt);
    return 0;
}

codeforces1209——D.Cow and Snacks（并查集）

热门文章

最新文章

相关电子书