P6134

james1BadCreeper · 2023-10-16 18:39:53 · 题解

注意到图是一个 DAG，因此对于一条边 (u,v)，如果删了这条边依然存在 u\rightarrow v 的间接路径，那么这条边必定被删去。

对于每个点求出它能到达的点和能到达它的点（不含自己）。如果 u 能到达的点和能到 v 的点有交集，那么这条边可以被删去。

前者每个点维护一个 bitset，按照拓扑序从大到小转移即可。后者建反图后跟前者一样。时间复杂度 O\left(\frac{nm}{\omega}\right)。

#include <bits/stdc++.h>
using namespace std; 

int n, m; 
int u[100005], v[100005], in[30005], a[30005]; 
vector<int> G[30005], E[30005]; 
bitset<30005> to[30005], fr[30005]; 

void Kahn(void) {
    queue<int> q; int tot = 0; 
    for (int i = 1; i <= n; ++i) if (!in[i]) q.push(i); 
    while (!q.empty()) {
        int u = q.front(); q.pop(); a[++tot] = u; 
        for (int v : G[u]) if (--in[v] == 0) q.push(v); 
    }
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= m; ++i) {
        cin >> u[i] >> v[i]; 
        G[u[i]].emplace_back(v[i]); E[v[i]].emplace_back(u[i]); 
        ++in[v[i]]; 
    } Kahn(); 
    for (int i = n; i >= 1; --i) {
        int u = a[i]; 
        for (int v : G[u]) to[u][v] = 1, to[u] |= to[v]; 
    }
    for (int i = 1; i <= n; ++i) {
        int u = a[i]; 
        for (int v : E[u]) fr[u][v] = 1, fr[u] |= fr[v]; 
    }
    int ans = 0; 
    for (int i = 1; i <= m; ++i) ans += (to[u[i]] & fr[v[i]]).any(); 
    cout << ans << "\n";
    return 0; 
}