桂林电子科技大学第三届ACM程序设计竞赛 F题

链接：https://ac.nowcoder.com/acm/contest/558/F
来源：牛客网
小猫在研究有向图。小猫在研究联通性。
给定一张N个点，M条边的有向图，问有多少点对(u,v)(u<v)，满足u能到达v且v也能到达u。
题意：给定一张N个点，M条边的有向图，问有多少点对(u,v)(u<v)，满足u能到达v且v也能到达u。
思路：跑一遍floyd，判断dis[u][v] != inf && dis[v][u] != inf 说明u -> v && v->u
#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
const int inf = 1e9;
int n, m, u, v;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = inf;
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        a[u][v] = 1;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && a[i][j] < inf && a[j][i] < inf) {
                ans++;
            }
        }
    }
    cout << ans / 2 << endl;
    return 0;
}