CCF Expressway (Tarjan algorithm, strong Unicom subgraph solution)


试题号: 201509-4
试题名称: 高速
@限 1.0s
@@@ @@Memory Limit:


问题描述某国有个城市,为了使得城市间的交通更便利,该国国王打算在城市之间修一些高速公路,由于经费限制,国王打算第一阶段先在部分城市之间修一些单向的高速公路。   现在,大臣们帮国王拟了一个修高速公路的计划。看了计划后,国王发现,有些城市之间可以通过高速公路直接(不经过其他城市)或间接(经过一个或多个其他城市)到达,而有的却不能。如果城市A可以通过高速公路到达城市B,而且城市B也可以通过高速公路到达城市A,则这两个城市被称为便利城市对。   国王想知道,在大臣们给他的计划中,有多少个便利城市对。


A city, in order to make the traffic between cities more convenient, the king of the country intends to be in the city Between the repair of some highways, due to financial constraints, the King intends to repair some one-way highways between some cities in the first phase. Now, the ministers have helped the king to plan a highway. After looking at the plan, the king found that some cities can be reached directly by highway (without other cities) or indirectly (via one or more other cities), while others cannot. If City A can reach City B by highway, and City B can also reach City A by highway, the two cities are called convenient city pairs. The king wanted to know how many convenient cities were in the plans the ministers gave him.

Input format n The first line of input contains two integers ,分别表示城市和单向高速公路的数量。   接下来m, which represent the number of cities and one-way highways, respectively. Next am, two integers per line b, indicating that the city b


has a one-way highway to the city

The output format

outputs a line containing an integer indicating the number of convenient city pairs.

5 5 1 2 2 3 3 4 4 2 3 5




  城市间的连接如图所示。有3个便利城市对,它们分别是(2, 3), (2, 4), (3, 4),请注意(2, 3)和(3, 2)看成同一个便利城市对。


评价用例尺寸和约定n ≤ 100, 1 ≤ 前的30%的评价用情况为1 ≤ ≤ 1000;   前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m|| |≤1000; The first 60% of the evaluation cases satisfy 1 ≤ ≤ 10000;   所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。


≤ 10000; All evaluation cases satisfy 1 ≤

This topic is not difficult, just apply the template of Tarjan algorithm directly. The detailed introduction of Tarjan algorithm can refer to the blog:

The following is the AC code of 100 points: