AcWing 3220. 高速公路
原题链接
中等
作者:
KeChang
,
2023-11-18 13:10:26
,
所有人可见
,
阅读 44
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10;
int n, m, idx, h[N], e[M], ne[M], timestamp, ssc_cnt, dfn[N], low[N], id[N], Cnt[N];
stack <int> stk;
bool in_stk[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int p) {
dfn[p] = low[p] = ++timestamp;
stk.push(p);
in_stk[p] = 1;
for(int i = h[p]; ~i; i = ne[i]) {
int u = e[i];
if(!dfn[u]) {
tarjan(u);
low[p] = min(low[p], low[u]);
}
else if(in_stk[u]) low[p] = min(low[p], dfn[u]);
}
if(low[p] == dfn[p]) {
int t;
++ssc_cnt;
do {
t = stk.top(); stk.pop();
in_stk[t] = 0;
id[t] = ssc_cnt;
++Cnt[ssc_cnt];
}while(t != p);
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
while(m--) {
int a, b;
cin >> a >> b;
add(a,b);
}
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i);
int ans = 0;
for(int i = 1; i <= ssc_cnt; ++i) {
int t = Cnt[i] - 1;
if(Cnt[i] > 1) ans += t + (t * (t - 1)) / 2 ;
}
cout << ans;
return 0;
}