思路大概就是让所有没得到最想要的稻草的奶牛在稻草的队列里面等候,每一次去除一个奶牛后用队列模拟,把其余的奶牛的状态进行更改。但很奇怪,有一个点过不了QAQ
附:code
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
queue<int>q[100100];
int f[100100],s[100100],sel[100100],vis[100100];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&f[i],&s[i]);
for(int i=1;i<=n;++i)
if(!vis[f[i]])
{
vis[f[i]]=1;
sel[i]=1;
++ans;
}
else if(!vis[s[i]])
{
vis[s[i]]=1;
++ans;
sel[i]=2;
q[f[i]].push(i);
}
else
{
sel[i]=3;
q[f[i]].push(i);
q[s[i]].push(i);
}
printf("%d\n",ans);
for(int i=1;i<n;++i)
{
int cur=f[i];
--ans;
while(!q[cur].empty())
{
int now=q[cur].front();
q[cur].pop();
if(sel[now]==2)
{
sel[now]=1;
cur=s[now];
}
else if(sel[now]==3)
{
++ans;
s[now]==f[cur]?sel[now]=1:sel[now]=2;
break;
}
}
printf("%d\n",ans);
}
return 0;
}