先不考虑第一喜欢和第二喜欢的区别,假设奶牛可以任意选择第一喜欢和第二喜欢。那么可以把奶牛看做无向边,麦片看做是顶点,建出一张无向图。
当然图不一定联通,考虑每个 \(x\) 点的联通块:
-
如果是树,那么有 \(x-1\) 条边,考虑浪费掉一个点(例如根),每条边选择儿子即可。在有第一喜欢和第二喜欢的情况下,这样做自然也是可行的。
-
如果不是树,那么至少有 \(x\) 条边。显然最多只有 \(x\) 只奶牛满足。考虑他的生成树(这里拿 DFS 树更方便)包含 \(x-1\) 条边,再随便选一条额外的边。我们先选择额外的边,它的第一喜欢的点设为根。其他边按照树做就行了。
于是每个连通块都最大化了,就做好了。
代码不够优美,仅供参考。
// By: Little09
// Problem: P8095 [USACO22JAN] Cereal 2 S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8095
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
#define printYes puts("Yes")
#define printYES puts("YES")
#define printNo puts("No")
#define printNO puts("NO")
const ll inf=1000000000000000000;
//const ll mod=998244353;
//const ll mod=1000000007;
const int N=100005;
int n,m;
int a[N],b[N];
vector<int>t[N],v[N];
vector<int>g[N],val[N];
inline int read()
{
int F=1,ANS=0;
char C=getchar();
while (C<'0'||C>'9')
{
if (C=='-') F=-1;
C=getchar();
}
while (C>='0'&&C<='9')
{
ANS=ANS*10+C-'0';
C=getchar();
}
return F*ANS;
}
inline char readchar()
{
char C=getchar();
while (C<33||C>126) C=getchar();
return C;
}
inline int raed(){return read();}
bool vis[N];
int s,num;
int ans[N],cnt;
bool used[N];
void dfs(int x,int fa)
{
num++;
vis[x]=1;
for (int i=0;i<t[x].size();i++)
{
if (v[x][i]==fa) continue;
if (vis[t[x][i]]==1)
{
if (s==-1)
{
s=a[v[x][i]];
ans[++cnt]=v[x][i];
used[v[x][i]]=1;
}
continue;
}
g[x].push_back(t[x][i]);
g[t[x][i]].push_back(x);
val[x].push_back(v[x][i]);
val[t[x][i]].push_back(v[x][i]);
dfs(t[x][i],v[x][i]);
}
}
void dfs2(int x,int fa)
{
for (int i=0;i<g[x].size();i++)
{
if (val[x][i]==fa) continue;
ans[++cnt]=val[x][i];
used[val[x][i]]=1;
dfs2(g[x][i],val[x][i]);
}
}
int main()
{
m=read(),n=raed();
for (int i=1;i<=m;i++)
{
a[i]=read(),b[i]=read();
t[a[i]].push_back(b[i]);
t[b[i]].push_back(a[i]);
v[a[i]].push_back(i);
v[b[i]].push_back(i);
}
int tot=0;
for (int i=1;i<=n;i++)
{
if (vis[i]==1) continue;
s=-1,num=0;
dfs(i,-1);
if (s==-1) tot+=num-1;
else tot+=num;
if (s==-1) dfs2(i,-1);
else dfs2(s,-1);
}
for (int i=1;i<=m;i++)
{
if (used[i]==0) ans[++cnt]=i;
}
cout << m-tot << endl;
for (int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
return 0;
}