Y - 孩子与玩具

有 n n n个小朋友， k k k个玩具，每个小朋友都有2个喜欢的玩具。

当他选择的时候，他会将他喜欢的玩具全部拿走。

求小朋友选择玩具的顺序，使得拿不到玩具的小朋友数量最少。

玩具是有限的，要使拿不到玩具的小朋友数量最少，就要使拿到2个玩具的小朋友最少。

也就是说，尽可能让拿到1个玩具的小朋友多。

于是就可以用贪心的思想：

首先，将一个小朋友喜欢的两个玩具连边，建图，

然后求一个最小生成树就可以了。

那么树上的一条边就代表一个小朋友，树上的一条路径就能表示一种小朋友选玩具的顺序。

显然一条路径上，只有第一个选的小朋友能选到两个玩具，其余小朋友都只能选到一个玩具，符合贪心的思想。

建图的时间复杂度是 O ( k ) O(k) O(k)的，并查集的复杂度可以近似认为是 O ( n ) O(n) O(n)的。

于是总的时间复杂度就是 O ( k + n ) O(k+n) O(k+n)。

生成树

并查集

贪心思想

#include 
#include 
#include 
#include 
#include 
#define G getchar
using namespace std;

int read()
{
    char ch;
    for(ch=G();ch<'0' || ch>'9';ch=G());
    int n=0;
    for(;'0'<=ch && ch<='9';ch=G())n=(n<<1)+(n<<3)+ch-48;
    return n;
}

const int N=100003;
int n,k,ans;
int f[N],x,y;

int get(int x){return(x==f[x]?x:f[x]=get(f[x]));}

int main()
{
    //freopen("y.in","r",stdin);
    //freopen("y.out","w",stdout);
    n=read();k=read();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=k;i++)
    {
    	x=read();y=read();
    	x=get(x);y=get(y);
    	if(x!=y)
    	{
    		ans++;
    		f[x]=y;
    	}
    }
    printf("%dn",k-ans);
}