P10179 水影若深蓝 题解

· · 个人记录

抽象题意

已知树 T 有 n 个节点，m 条约束，每条约束形如 u_i\rightarrow v_i 的简单路径包含 2 条树边。

构造树 T。

构建模型

我们设 dep_u 为节点 u 的深度（dep_{root}=0，dep_u=dep_{fa_u}+1）。

约束转为：① u_i,v_i 为兄弟关系（此时 dep_{u_i}=dep_{v_i}） 或 ② u_i,v_i 为祖孙关系（此时 |dep_{u_i}-dep_{v_i}|=2）。

下证，若存在树 T，则必然存在一解，满足树 T 的层数 \le 3：

对于任意满足约束 且 层数 >3 的树 T，最底层的节点约束必定只与同层节点 及 上上层节点有关。对于最底层的节点 u，我们把它移至上上层，与它的爷爷同认一个爹。操作后，u 与其爷爷的约束仍然满足，而它的兄弟与它共有一个爷爷，因此 u 与其兄弟的约束也仍然满足。以次类推，得一层数 =3 的树 T'，仍满足约束。

证毕。

求解问题

考虑已知 root，如何 O(n) 求树 T。

先将所有与 root 有约束的节点加入第 3 层。

再将所有与第 3 层节点有约束的节点加入第 3 层。

以次类推，类似搜索联通块。

余下的节点加入第 2 层。

第 2 层节点数 >0，有解，否则无解。

有解时，将 root 与所有第 2 层节点连边，任取一第 2 层节点与所有第 3 层节点连边，即得一颗满足约束的树 T。

问题：如何求 root。

构建图论模型，对于所有约束 (u_i,v_i)，都连一条双向边 u_i\leftrightarrow v_i，得图 G。root 满足约束，当且仅当，图 G 除去 root 所在连通块后，仍余下至少 1 个节点（连通块）。因此 root 取哪个节点都无异，是否存在解仅仅取决于图中是否存在多个连通块。

第一层：root。

第三层：root 所在连通块中除 root 外的节点。

第二层：root 所在连通块外的节点。

代码实现

两种方法：

① DFS O(n) 求解，代码略显冗长。

② 并查集 O(nlogn) 求解，清新健康。

后者代码：

#include<bits/stdc++.h>
using namespace std;
const int N=300005;
int T,n,m; 
int fa[N];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]); 
}
void merge(int u,int v){
    u=find(u),v=find(v);
    fa[u]=v;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) fa[i]=i;
        while(m--){
            int u,v;scanf("%d%d",&u,&v);
            merge(u,v);
        }
        int f=find(1);
        int x=-1;
        for(int i=2;i<=n;i++){
            if(f!=find(i)){x=i;break;}
        }
        if(x==-1){puts("No");continue;}
        puts("Yes");
        for(int i=2;i<=n;i++){
            if(f!=find(i)) printf("%d %d\n",1,i);
        }
        for(int i=2;i<=n;i++){
            if(f==find(i)) printf("%d %d\n",x,i);
        }
    }
    return 0;
}