自动搬运

查看原文

来自洛谷，原作者为

	elbissoPtImaerD Just keep it Quiet, it'll be all right. :-)

搬运于2025-08-24 22:56:10，当前版本为作者最后更新于2024-06-03 23:00:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题主要考察的知识点：【9】构造思想。

比较好写的线性做法。

不妨考虑那 $0$ 作为每个点的答案，显然会有若干点不合法， 不妨先考虑 $\forall i, u_0 \in \{u_i,v_i\}$ 的答案。考虑再找一个 $j$ 使得 $j$ 是 $i$ 的答案。首先显然不能找 $u_0 \in \{u_j,v_j\}$ 的 $j$，再随便从剩下的找一个 $j$，那么不能以 $0$ 和 $j$ 作为答案的 $i$ 必然满足 $(u_i \in \{u_j,v_j\}\wedge v_i=x_0)\vee(u_i=x_0 \wedge v_i \in \{u_j,v_j\})$，这样的显然只有 $O(1)$ 个，直接暴力扫答案即可。

extern "C" int*find_pairs(int m,int n,int u[],int v[]) {
  int*ans=new int[n];
  fill(ans,ans+n,-1);
  const auto chk=[&](int i,int j) {
    if(u[i]!=u[j]&&u[i]!=v[j]&&v[i]!=u[j]&&v[i]!=v[j]) {
      ans[i]=j,ans[j]=i;
      return true;
    }
    return false;
  };
  ve<int>b[2],p[2];
  for(int i=1;i<n;++i) {
    if(chk(0,i)) p[0].pb(i),p[1].pb(i);
    else b[u[i]!=u[0]].pb(i),p[u[i]==u[0]].pb(i);
  }
  for(int _:{0,1}) if(p[_].size()) {
    for(int i:b[_]) if(!chk(i,p[_][0])) {
      for(int j:p[_]) if(chk(i,j)) break;
    }
  }
  return ans;
}