a,b,c,d 构成“菱形”当且仅当存在有向边 a→b, b→c, a→d, d→c。(a,c),设能把 a 接到 c 的不同中间点(即 a→x 且 x→c 的点)个数为 k,则可由它们两两配对形成 C(k,2) 个菱形。a,遍历所有两步路径 a→b→c,用数组 cnt[c] 统计到该 c 的不同中间点数;只记录出现过的 c(列表 touched),最后对每个被访问的 c 把 C(cnt[c],2) 加入答案。遍历时排除 c==a 和 c==b,同时忽略自环 u==v,以确保四点互异。小明来到一个新的城市,当他看到城市里四个不同的地点 a、b、c 和 d 时,如果存在两条从 a 到 c 的路径————一条通过 b ,另一条通过 d,他就称这个四个地点组合为“菱形”。
菱形的定义:
a、b、c、d 四个不同的地点,满足以下条件:
(a,b)、(b,c)、(a,d)、(d,c) 这些道路是直接连接的。