P10179 水影若深蓝题解

yshpdyt · 2024-02-21 15:15:55 · 题解

题意

对于一颗 n 个点的树，给定 m 条如下关系：对于给定的 u,v，满足 u \to v 的树上唯一简单路径距离的为二，简单来说就是这两个结点之间隔了一个节点，构造出任意符合要求的树，或报告无解。

Sol

对于每一条关系，用类似存无向图的方式记录，即 u 连向所有与其隔一个点的结点。

然后我们可以假设一个虚拟结点为 t_1，随便取一个结点 u，认为所有与 u 存在关系的点 v，两点之间恰好相隔 t_1，也就是如下图：

这样做的好处就是保证了 u 的关系都得到满足，并且不会破坏其余 v 的关系。

接着我们考虑所有 v 的关系，用与刚才类似的方法进行构造，不难得到下图。

像这样类似拓扑排序的进行下去，用队列维护，每次取出队首，把所有与队首有关系的结点都让其与 t_1 相连，然后加入队列，重复操作，直到队列为空，这样可以构造出一颗菊花图。

但是这样的操作还存在两个缺陷，有的关系还没有在图上体现， t_1 结点还不确定。

如何解决？我们可以再构造多个菊花图，对于两个不在同一个图上的点，他们之间没有关系，互不影响：

注意加黑的点，我们可以让 t_1 变成 x，让 t_2 变成 u 合并一下：

对于其他的虚拟结点，只需要让 t_3,t_4,t_5 都等于 t_1 即可，也就是图中的 x，这里不再放图，自行想象 x 左右还连着若干对点。

没有任何关系的点也可以与 x 相连。

这样的正确性显然，两个图之间的点不存在任何关系，合并图只是让虚拟结点变成实际的结点，选用一个毫不相干的点作为其核心结点，当然不受影响。

对于无解情况，如果所有点都与 t_1 相连，那么无法找到 t_2 ，也就是另一个菊花图，从而导致没有点可以代替 t_1，导致无解。

考虑一下代码如何实现。

初始化所有 res[u]=0，认为所有结点都为孤立点。

取任意结点作为 t_1 ，设虚拟结点为 t_2，用类似拓扑排序的方式把所有有关结点都与 t_2 相连，因为不知道 t_2，可以令 res[u]=2 。

遍历所有结点，如果该结点还没有与 t_2 相连，让该结点成为 t_2，重复刚才类似拓扑排序的操作，把所有有关结点都与 t_1 相连，可以令 res[u]=1 。

特别的，如果所有结点都与 t_2 相连，那么无解。

最后输出，如果 res[u]=2，输出 (u,t_2)，如果 res[u]\le 1 输出 (u,t_1)，特别的，注意到 res[t_2]=1 且 res[t_1]=2，这样会输出两次，特判去掉即可，刚好 n-1 次。

本题的核心思路在于想到菊花图，并且进行合并。

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

Code

#include<bits/stdc++.h>
#define ll long long
#define N 400005
#define endl "\n" 
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n,m,res[N],tr[3];
bool vis[N];
vector<ll>v[N];
queue<ll>q;
void sol(){
    cin>>n>>m;
    tr[1]=tr[2]=0;
    for(int i=1;i<=n;i++){
        v[i].clear();
        vis[i]=0;
        res[i]=0;
    }
    while(!q.empty())q.pop();
    for(int i=1;i<=m;i++){
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bool fl=1;
    for(int i=1;i<=n;i++){
        if(!tr[1]){
            tr[1]=i;
            break;
        }
    }
    q.push(tr[1]);
    res[tr[1]]=2;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        vis[t]=1;
        for(auto y:v[t]){
            if(!vis[y]){
                q.push(y);
                res[y]=2;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            tr[2]=i;
            break;
        }
    }
    if(!tr[2]){
        cout<<"No\n";
        return ;
    }
    q.push(tr[2]);
    res[tr[2]]=inf;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        vis[t]=1;
        for(auto y:v[t]){
            if(!vis[y]){
                q.push(y);
                res[y]=1;
            }
        }
    }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        if(res[i]<=2){
            if(res[i]==0)res[i]=1;
            cout<<i<<" "<<tr[res[i]]<<endl;
        }
    }
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll ttt;
    cin>>ttt;
    while(ttt--)sol();
    return 0;
}

P10179 水影若深蓝 题解

题意

Sol

Code

P10179 水影若深蓝题解