2019河北省大学生程序设计竞赛（重现赛）J-舔狗 （拓扑排序）

题目链接：https://ac.nowcoder.com/acm/contest/903/J

---

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

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

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

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<queue>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int maxn = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 int n;

 int in[maxn];

 int vis[maxn];

 int like[maxn];

 struct node{

     int u,v;//u是编号，v是入度。

     bool friend operator<(node a,node b)//优先队列使入度小的排在前面

     {

         return a.v > b.v;

     }

 };

 void solve()

 {

     int ans = ;

     priority_queue<node> q;

     for(int i = ;i<= n;i++)

     {

         q.push( node{i,in[i]} );//将所有点加入队列;

     }

     while(!q.empty())

     {

         node w = q.top(); q.pop();

         if(vis[w.u] || vis[ like[w.u] ]) continue; //如果他或者他喜欢的配对了就不能配了;

         ans += ;

         vis[w.u] = ;

         vis[ like[w.u] ] = ;

         //更新入度，反正优先队列，多跑几次没关系

         q.push( node{like[like[w.u]],--in[ like[like[w.u]] ] } );//like[like[w.u]] 是指舔狗喜欢的人喜欢的人。

     }

     printf("%d\n",n-ans);

 }

 int main()

 {

     scanf("%d",&n);

     for(int i = ;i <= n;i++)

     {

         scanf("%d",&like[i]);

         in[like[i] ]++;

     }

     solve();

     return ;

 }