首页 > 其他分享 >AT ARC092F Two Faced Edges

AT ARC092F Two Faced Edges

时间:2022-08-17 08:57:35浏览次数:72  
标签:Faced 存在 一条 联通 ARC092F 路径 Edges 反向 条边

题意:给定一个有向图,保证无重边自环,求将图中的每条边反向后强联通分量的个数是否会改变。

数据范围:$n$ $≤$ $1000$,$m$ $≤$ $200000$。

首先考虑一条边的影响。

因为一条边只能连接两个点,因此将一条边反向至多只能影响它两个端点在强联通分量里的变化,即整体增加一个强联通分量,或整体减少一个强联通分量(或整体不变)。

再考虑将这条边反向之前,两端点 $u$,$v$ 之间的联通情况。

假设这条边为 $u$ $→$ $v$,那么将这条边反向,在图中就可以看作增加一条 $v$ $→$ $u$ 的边,删掉一条 $u$ $→$ $v$ 的边。

那么在删边和添边之前,考虑 $4$ 种情况。

  • 存在一条 $u$ $→$ $v$ 的路径,且其中不包含 $u$ $→$ $v$ 这条边;存在一条 $v$ $→$ $u$ 的路径;
  • 存在一条 $u$ $→$ $v$ 的路径,且其中不包含 $u \to v$ 这条边;不存在一条 $v$ $→$ $u$ 的路径;
  • 不存在不经过 $u$ $→$ $v$ 这条边的一条 $u$ $→$ $v$ 的路径 ;存在一条 $v$ $→$ $u$ 的路径;
  • 不存在不经过 $u$ $→$ $v$ 这条边的一条 $u$ $→$ $v$ 的路径 ;不存在一条 $v$ $→$ $u$ 的路径;

 

标签:Faced,存在,一条,联通,ARC092F,路径,Edges,反向,条边
From: https://www.cnblogs.com/louis660/p/16593668.html

相关文章

  • ARC092F口胡
    对一条边\((u,v)\)分两种情况讨论:在原图中是否属于强连通分量。如果属于一个强联通分量:考虑一对节点\((x,y)\),若\((x,y)\)路径上\((u,v)\)为必经之路,且\(y\)可......