思路：每个舔狗只会喜欢一个人，每个人的选择就只有一个，要满足配对的舔狗数量最多，我们就应该选择喜欢人数少的舔狗来优先进行匹配。一个舔狗被多少人喜欢，就是这个点的入度。如果喜欢他的其中一个舔狗被配对了，那么这个舔狗的入度就应该减去1。我们就利用优先队列来维护每个舔狗的入度，然后去判断是否可以帮这只舔狗配对。
///#include<bits/stdc++.h> ///#include<unordered_map> ///#include<unordered_set> #include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<queue> #include<set> #include<stack> #include<map> #include<new> #include<vector> #define MT(a, b) memset(a,b,sizeof(a)) #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; typedef unsigned long long ull; const double pai = acos(-1.0); const double E = 2.718281828459; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; const int maxn = 1e6 + 5; int n,like[maxn],in[maxn]; int vis[maxn],ans; struct node{ int e,d; bool friend operator<(node a,node b){ return a.d>b.d; ///优先选择入度少的舔狗 } }; void solve(){ priority_queue<node>q; for(int i=1;i<=n;i++){ q.push(node{i,in[i]}); } while(!q.empty()){ node w=q.top(); q.pop(); ///如果已经被选择,或者他喜欢的人也配对了 if(vis[w.e]||vis[like[w.e]]) continue; ans+=2; vis[w.e]=vis[like[w.e]]=1;///这两只舔狗配对 ///舔狗喜欢的人的入度减去1 q.push(node{like[like[w.e]],--in[like[like[w.e]]]}); } printf("%d\n",n-ans); ///输入未配对的舔狗数 } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&like[i]); in[like[i]]++; } solve(); return 0; }
