自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:19:03，当前版本为作者最后更新于2020-04-01 19:58:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

连通分量是一棵树

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

连通分量不是一棵树

这种情况下，如果一条 $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;
}