试题编号： 201509-4 试题名称： 高速公路 时间限制： 1.0s 内存限制： 256.0MB
问题描述：
问题描述 某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高速公路。 现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。 国王想知道，在大臣们给他的计划中，有多少个便利城市对。 输入格式 输入的第一行包含两个整数n, m，分别表示城市和单向高速公路的数量。 接下来m行，每行两个整数a, b，表示城市a有一条单向的高速公路连向城市b。 输出格式 输出一行，包含一个整数，表示便利城市对的数量。 样例输入
5 5
1 2
2 3
3 4
4 2
3 5
样例输出
3
样例说明 城市间的连接如图所示。有3个便利城市对，它们分别是(2, 3), (2, 4), (3, 4)，请注意(2, 3)和(3, 2)看成同一个便利城市对。 评测用例规模与约定 前30%的评测用例满足1 ≤ n ≤ 100, 1 ≤ m ≤ 1000； 前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000； 所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。
思路
强连通分量，我一开始还不会的时候直接用数学组合，还有40分还不错hhh，学了tarjin算法，都说另一个简单，我总觉得还是tarjin比较好理解= =。
实现代码
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std
;
const int maxn
= 10000 + 5;
int n
, m
, s
, e
, cnt
= 0, ans
= 0;
int dfn
[maxn
], low
[maxn
], instack
[maxn
];
vector
<int> Edges
[maxn
];
stack
<int> st
;
void tarjin(int begin
) {
low
[begin
] = dfn
[begin
] = ++cnt
;
st
.push(begin
);
instack
[begin
] = 1;
for (int i
= 0; i
< Edges
[begin
].size(); i
++) {
int to
= Edges
[begin
][i
];
if (!dfn
[to
]) {
tarjin(to
);
low
[begin
] = min(low
[begin
], low
[to
]);
}
else if(instack
[to
]) low
[begin
] = min(low
[begin
], dfn
[to
]);
}
if (low
[begin
] == dfn
[begin
]) {
int num
= 0;
while (1) {
num
++;
int index
= st
.top();
st
.pop();
instack
[index
] = 0;
if (index
== begin
) break;
}
if(num
> 1) ans
+= num
* (num
- 1) / 2;
}
}
int main() {
memset(instack
, 0, sizeof (instack
));
memset(low
, 0, sizeof (low
));
memset(dfn
, 0, sizeof (dfn
));
cin
>> n
>> m
;
for (int i
= 1; i
<= m
; i
++) {
cin
>> s
>> e
;
Edges
[s
].push_back(e
);
}
for (int i
= 1; i
<= n
; i
++) if (!dfn
[i
]) tarjin(i
);
cout
<< ans
<< endl
;
return 0;
}
