题解 P6255 【[ICPC2019 WF]Dead-End Detector】

· · 题解

对于每个连通分量分两种情况来讨论。

连通分量是一棵树

此时按题目要求，从任何一个点出发选任何一条边都是死路。但事实上，只需要在叶节点处标记从叶节点出发的边即可（这些标记已经可以完整覆盖所有死路了）。

连通分量不是一棵树

这种情况下，如果一条 u \to v 边满足其被割断后图分为两个连通分量，且 v 所在连通分量是一棵树，那么就可以在 u 入口处安装标记。

这样可能会存在重复覆盖的情况，我们可以这样做：逐步删除所有叶子节点，直到无法再删为止，那么从没被删的点 u 到被删的点 v 之间就是死路。

这个标记完整覆盖了 v 所处的子树，从而避免了不必要的标记。

// Problem : P6255 [ICPC2019 WF]Dead-End Detector
// Contest : Luogu Online Judge
// URL : https://www.luogu.com.cn/problem/P6255
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 1000 MB
// Time Limit : 5000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
int t[500005],vis[500005];
vector<int> e[500005],l,p[500005];
vector<pair<int,int> > res;
queue<int> q;
set<int> s;
void dfs(int u)
{
 vis[u]=1;
 s.insert(u);
 if(t[u]==1)
 {
  q.push(u);
  l.push_back(u);
 }
 for(auto v:e[u])
  if(!vis[v])
   dfs(v);
}
int main()
{
 ios::sync_with_stdio(false);
 int n,m;
 cin>>n>>m;
 for(int i=1;i<=m;i++)
 {
  int u,v;
  cin>>u>>v;
  e[u].push_back(v);
  e[v].push_back(u);
  t[u]++,t[v]++;
 }
 for(int i=1;i<=n;i++)
  if(!vis[i])
  {
   s.clear();
   l.clear();
   dfs(i);
   while(!q.empty())
   {
    int u=q.front();
    q.pop();
    s.erase(u);
    for(auto v:e[u])
    {
     t[v]--;
     if(t[v]==1)q.push(v);
    }
   }
   if(s.empty())
    for(auto u:l)
     res.push_back({u,e[u].front()});
   else
    for(auto u:s)
     for(auto v:e[u])
      if(!s.count(v))
       res.push_back({u,v});
  }
 sort(res.begin(),res.end());
 cout<<res.size()<<endl;
 for(auto p:res)
  cout<<p.first<<' '<<p.second<<endl;
 return 0;
}