题解：AT_arc211_d [ARC211D] Michishirube

· · 题解

不错的算法、构造的综合思维题，可能这种做熟练了也感觉偏典？

本题概要题意：给定一张简单无向连通图，指定节点 1 为蓝色终点，2 为黄色终点，对于每个节点（除终点），你需要选择两条不同的边标上蓝/黄箭头，使得任意节点都能按蓝/黄箭头指向到达相应颜色终点。

简单分析性质，很难不发现，标上每种颜色的边数均为 n-1 条，所有点都能到达终点等价于该颜色的边形成一棵以终点为根，所有边指向深度较小节点的树。

分析上述性质，我们考虑先对蓝色跑一种合法方案（生成树）。为防止横叉边的干扰，在这里我们采用 DFS 生成树。此时我们要做到利用树边向下、非树边反祖来使所有点都能到达 2（树边不能向上重复利用）。

继续考虑如何达到这一效果。对于节点 2 的祖先节点，显然一路向下即可。对于其他节点，我们考虑一种贪心的想法，即越往深度小处走越有可能到达节点 2，因为没有横叉边的情况下所能到的深度最小的点一定能通过树边向下到达其余能到的点。

如何走到最小深度呢？显然可以从下到上遍历树，记录当前节点所能到的最小深度，若儿子节点能到达更小深度，则将箭头指向能到达最小深度的儿子节点，否则指向该点所连非树边中能到深度最小的节点。

现在我们获得了构造方案，下证直接以这种方式判断出有无解的充要性。在这种构造方式下，无解当且仅当某节点无法跳到深度足够小处，而这表明该节点有一条必经树边才能向上到达深度更小以致能到达 2，显然找不出任何构造方案使得其绕过通往 1 和 2 的必经之路，故无解。由此可知，只要有解，这种构造一定能找出来。于是本题就做完了。

::::success[code]


#include<bits/stdc++.h>
using namespace std;
int n,m,pa[200010],low[200010],p[200010],d[200010],cntt;
//low 所能到达最小深度，p 黄箭头指向
vector <int> b[200010],son[200010],fs[200010],fp[200010];
//fs 非树边，fp 反黄边
bool vis[200010];
//建树
void dfs1(int id)
{for(int i=0;i<b[id].size();i++)
 {if(!d[b[id][i]])
  {pa[b[id][i]]=id;son[id].push_back(b[id][i]);
   d[b[id][i]]=d[id]+1;dfs1(b[id][i]);
  }
  else if(b[id][i]!=pa[id])
  fs[id].push_back(b[id][i]);
 }
}
//定向
void dfs2(int id)
{int _min=d[id]+1,min_id;
 for(int i=0;i<son[id].size();i++)
 {dfs2(son[id][i]);
  if(low[son[id][i]]<_min)
  {_min=low[son[id][i]];
   min_id=son[id][i];
  }
 }
 for(int i=0;i<fs[id].size();i++)
 {if(d[fs[id][i]]<_min)
  {_min=d[fs[id][i]];
   min_id=fs[id][i];  
  }
 }
 low[id]=_min;
 if(p[id]==0)
 {p[id]=min_id;fp[min_id].push_back(id);}
}
//判可行
void dfs3(int id)
{vis[id]=true;cntt++;
 for(int i=0;i<fp[id].size();i++)
 {if(!vis[fp[id][i]])
  dfs3(fp[id][i]);
 }
}
int main()
{cin>>n>>m;
 for(int i=1,u,v;i<=m;i++)
 {cin>>u>>v;
  b[u].push_back(v);b[v].push_back(u);
 }
 d[1]=1;
 dfs1(1);
 for(int i=1;i<=n;i++)
 low[i]=d[i];
 int id=2;
 while(pa[id]!=0)
 {p[pa[id]]=id;fp[id].push_back(pa[id]);
  id=pa[id];
 }
 dfs2(1);
 dfs3(2);
 if(cntt!=n) {cout<<"No";return 0;}
 cout<<"Yes\n";
 cout<<p[1]<<'\n'<<pa[2]<<'\n';
 for(int i=3;i<=n;i++)
 cout<<pa[i]<<' '<<p[i]<<'\n';
}