【Date】

【问题描述】

小SYH和小LCR好不容易有机会约会啦,可是邪恶的小YJQ却不想让他们相见。现在有一些城市,城市之间有双向路径相连,有路径相连的城市之间可以互相到达。小YJQ可以任意选择一条路径,然后用他FFF团的怒火烧毁这条路径,使得它不能被通行。虽然小SYH和小LCR在千辛万苦之后相遇了,但是小LCR非常害怕。她想让小SYH告诉她,他们初始在哪些点对上,小YJQ就可以选择任意一条路径烧毁使得他们不能相见。

【输入格式】

第一行两个数字N和M。N表示城市数,M表示路径数。

第二行到第M+1行,两个数a和b,其中1≤a,b≤N,表示a和b之间有路径相连。

【输出格式】

输出一个整数,表示所求点对的数量。

【输入样例】

2 1

1 2

【输出样例】

1

【样例说明】

点对(1,2)满足不能相见的条件。

【数据范围】

对于100%的输入数据:1≤N≤20000,1≤M≤40000

注:两个点对本来就不能到达的情况也要算。

这种题点对可以分成3种:

①两个点对本来就不能到达。

②处在全图森林中某一颗树上连通。

③处在双连通分量中。

显然前两种都可以被切断而后一种不可以。

所以计算所有点对数目再减掉每个双联通分量的点对数目就行了。

计算双连通分量嘛,Tarjan稍微加个走过的边标记就行啦~

PS:强连通分量又叫单连通分量,而双连通分量是在单连通分量的基础上,即使删除某条边分量中所有点也还是能互相到达的分量。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*