题目描述
牛牛有n个朋友,标号为0到n-1,每一个朋友最多有一个不喜欢的人,记为a[i],如果第i个人喜欢每一个人,a[i]=i
现在牛牛需要邀请每一个人来参加一个聚会,但是他发现不同的邀请顺序会导致不同的结果,因为一旦某个人发现他不喜欢的人已经被邀请了,他就不会来参加聚会,请问最多可以邀请多少个人来参加聚会.
输入描述:
第一行输入一个整数n (1≤n≤50)
第二行输入n个整数
ai 0≤ai≤n−1
输出描述:
输出一个整数
题目分析:
做题过程中感觉这绝不是简单的贪心问题,还加上了并查集的知识,首先在过程中把喜欢自己的淘汰掉,因为它喜欢所有人,只要最后邀请就好了,它肯定回来的。然后就进行判断,找每个点的根,一旦形成一个圈,最后的答案就要减去一,因为一旦形成了圈,不管你怎样邀请,都会有一个人不回来的。
欢迎大家积极讨论,我会积极为大家解答问题,最后别忘了给作者点个赞哦!
#include <cstdio> #include <iostream> using namespace std; int a[55]; int find(int num) { if(num==a[num])return num; else return find(a[num]); } int main () { int n; cin >> n; int ans=n; for (int i=0;i<n;i++) { a[i]=i; } for (int i=0;i<n;i++) { int num; cin >> num; if(num==i)continue; int x=find(num); if(x==i) { ans--; } else { a[i]=x; } }