P8095 Cereal 2 S 题解

· · 题解

有趣的题。

碰到这种二元关系的题，我们通常可以考虑从图论的角度去思考。

具体地说，我们把麦片当作点，把奶牛当作边。

我一开始考虑把奶牛当作有向边，从第一喜欢的麦片指向第二喜欢的麦片，但是有向图没有什么好的性质。

所以我们不妨把奶牛看作无向边，再考虑它是否满足题目条件。

考虑每个连通块，设连通块内能够吃到麦片的奶牛数为 cnt，连通块点数为 n，边数为 m。

显然 cnt\le \min(n,m)。

通过手玩几组数据，我们不妨大胆猜想 cnt= \min(n,m)。

具体地说，如果 m=n-1，即连通块是一棵树，则 cnt=n-1；否则 cnt=n。

接下来我们考虑如何构造。

  1. 从连通块内任意一个节点开始 bfs/dfs，按照 bfs/dfs 顺序输出边即可。 **正确性说明：** 设一条边为 $(u,v)$，其中 $u$ 是 $v$ 在树上的祖先。 在访问到这条边的时候，$v$ 一定没有被选择，$u$ 可能被选可能不被选。 所以不论这条边的指向如何，它都一定能够被满足。 所以恰好有 $m=n-1$ 条边被满足，方案是正确的。
  2. 我们考虑建出连通块的一棵搜索树，这时候我们还要使得连通块内的一条后向边（即不在搜索树上的边）被满足。 所以我们不妨先输出一条后向边，设这时被选择的点（即第一喜欢的麦片）为 $s$。 以 $s$ 为根对搜索树进行 bfs/dfs，按照顺序输出树上的边。 最后再输出不能被满足的边即可。 **正确性说明：** 依然考虑边 $(u,v)$，其中 $u$ 是 $v$ 在树上的祖先。 如果 $u=s$，显然只能选择 $v$。 否则按照数学归纳法，$u$ 一定已经被选择，所以不论 $v$ 是不是第一选择，都只能选择 $v$。 这时有恰好 $n$ 条边被满足，方案是正确的。

时间复杂度为 O(n+m)。

#include<bits/stdc++.h>
#define N 100009
using namespace std;
int n,m,ans,hd[N],tot,fi[N],c[N],nV[N],nE[N],nC,choose[N];
bool in[N<<1],vst[N];//in代表在不在搜索树内,vst代表有没有被选
struct edge{
    int t,nxt;
} es[N<<1];
//编号为i的边为(i*2)和(i*2+1)
void add(int u,int v){es[++tot]=(edge){v,hd[u]},hd[u]=tot;}
void dfs(int u){
    ++nV[c[u]];
    for(int i=hd[u];i;i=es[i].nxt){
        ++nE[c[u]];
        int v=es[i].t;
        if(c[v])continue;
        in[i]=in[i^1]=1;
        c[v]=c[u];
        dfs(v);
    }
}
void print(int u,int in_edge){
    for(int i=hd[u];i;i=es[i].nxt)if(in[i]&&i!=(in_edge^1)){
        printf("%d\n",i>>1);vst[i>>1]=1;
        print(es[i].t,i);
    }
}
int main(){
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=n;++i){
        int u,v;scanf("%d%d",&u,&v);fi[i]=u;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;++i)
        if(!c[i]){
            c[i]=++nC;
            dfs(i);
        }
    for(int i=1;i<=n;++i)if(!in[i<<1]){//第二种情况(选择一条后向边)
        int id=c[es[i<<1].t];choose[id]=i;
    }
    for(int i=1;i<=m;++i)if(nE[c[i]]==nV[c[i]]*2-2)
        choose[c[i]]=i;//第一种情况（dfs起始点）
    ans=m;
    for(int i=1;i<=nC;++i)
        if(nE[i]==nV[i]*2-2)--ans;
    cout<<n-ans<<endl;
    for(int i=1;i<=nC;++i){
        if(nE[i]==nV[i]*2-2){
            print(choose[i],0);
        }else{
            printf("%d\n",choose[i]);vst[choose[i]]=1;
            print(fi[choose[i]],0);
        }
    }
    for(int i=1;i<=n;++i)
        if(!vst[i])printf("%d\n",i);
    return 0;
}