题目链接：

---

题意：给你 n 个舔狗和他喜欢的人，让你俩俩配对（只能和喜欢它的和它喜欢的），求剩下的单身狗数量。

思路：类似于拓扑排序，由入度最少的边开始配对，也就是被最少的舔狗喜欢的（甚至是没有）。将已经配对的舔狗进行标记，更新入度后重新加入优先队列，最后用总数减去标记数就是答案了。

总结：一开始我的思路是对的呐，但是我太菜了，卡在没办法处理同时配对2个点和维护他们入度，看完别人的处理才发现自己是局限于找入度为0而不是找入度最少。

AC代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int maxn = 1e6 + 5; 8 const int INF = 0x3f3f3f3f; 9 int n;10 int in[maxn];11 int vis[maxn];12 int like[maxn];13 struct node{14     int u,v;//u是编号，v是入度。15     bool friend operator<(node a,node b)//优先队列使入度小的排在前面16     {17         return a.v > b.v;18     }19 };20 void solve()21 {22     int ans = 0;23     priority_queue
          
            q;24 for(int i = 1;i<= n;i++)25 {26 q.push( node{i,in[i]} );//将所有点加入队列;27 }28 while(!q.empty())29 {30 node w = q.top(); q.pop();31 if(vis[w.u] || vis[ like[w.u] ]) continue; //如果他或者他喜欢的配对了就不能配了;32 ans += 2;33 vis[w.u] = 1;34 vis[ like[w.u] ] = 1;35 //更新入度，反正优先队列，多跑几次没关系36 q.push( node{like[like[w.u]],--in[ like[like[w.u]] ] } );//like[like[w.u]] 是指舔狗喜欢的人喜欢的人。37 }38 printf("%d\n",n-ans);39 }40 int main()41 {42 scanf("%d",&n);43 for(int i = 1;i <= n;i++)44 {45 scanf("%d",&like[i]);46 in[like[i] ]++;47 }48 solve();49 return 0;50 }