P10248 解题报告

elbissoPtImaerD · 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;
}