对于一个 |V| 个点 (每个点从 1 到 |V| 编号)，|E| 条边的有向图，scx 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。

scx 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？

为了简化一下大家的工作量，这次 scx 保证他给定的有向图一定是一个有向无环简单图。

(scx: 经过讨论，我们都知道对于任意有向图的，都可以通过 ~~Tarjan 缩点~~转化为有向无环图上的问题)。

输入格式

输出格式

题解

可以知道如果一条边 (u, v) 可以被删，说明存在一点 w，存在从 u 到 w 以及从 w 到 v 的路径。换句话说，就是从 u 到 v 存在一条长度超过 1 的路径。

因此，我们可以倒着遍历拓扑序，设拓扑序中最后一个点 (也就是出度为 0 的点) 为 x，可以在拓扑排序的时候，或者在遍历的时候，统计出每个点 u 到点 x 的最长路径的长度 dist(u)。

当遍历到点 u 时，考虑点 u 的邻域 N(u) (也就是以 u 作为起点的边的终点的集合)，按照 dist 函数值从大到小排序，记录这个点能到达哪些点。如果在访问 N(u) 中点 v₀ 的时候，发现之前的点所能到达的点的集合中有 v₀，不妨设通过 v₁ 可以到达 v₀，不难发现，这条边就没用了 (因为从 u 到 v₀ 可以经过点 v₁)。

对于边 (u, v)，且点 u 到点 v 之间存在一条长度超过 1 的路径，不妨设这条路径中点 u 连接了点 w。那么，可以~~比较显然地~~发现，dist(w) > dist(v)，且 v, w 的拓扑序一定在点 u 后，所以遍历到点 w 的时候，可以发现，可以到达点 v，就记录下来，再访问到点 v 的时候，就可以把这条边删掉了。

(scx: 那如何记录点 u 通过 N(u) 中的一部分点能到达哪些点呢？)

由于|V| ≤ 30000，我们就可以采用 bitset 大法，开 |V| 个 bitset，第 u 个 bitset 记录从 u 出发能到达哪些点，空间为 $\Theta(\frac{|V|^2}\omega)$ ，其中 ω 为机器字长 ∈ {32, 64}，显然不会爆，并且要记录 N(u) 中前 k 个点能到达哪些点，只要不停地使用 | (or) 操作即可。

分析一下时间，拓扑排序为 $\Theta(|E|)$ ，后期操作基本就是 $\Theta(\frac{|V|^2}\omega+|E|)$ 和空间同一个数量级，不会 TLE 的。

代码

#include <bits/stdc++.h>
#define maxV 30034
#define maxE 100034
using namespace std;

struct edge{
    int u, v;
    edge(int u0 = 0, int v0 = 0): u(u0), v(v0) {}
};

typedef vector <int> vec;

int V, E, i, j;
int u, v;
int first[maxV], next[maxE], deg[maxV], que[maxV];
int pass[maxV], dist[maxV], cnt, ans;
edge e[maxE];
vec Topo;
bitset <maxV> con[maxV];

inline void addedge(int u, int i){next[i] = first[u]; first[u] = i;}
inline void up(int &x, int y){x < y ? x = y : 0;}
inline bool cmp(const int &A, const int &B){return dist[A] > dist[B];}

void TopoSort(){
    int h, t = 0, u, i;
    for(i = 1; i <= V; i++)
        if(!deg[i]) que[t++] = i;
    for(h = 0; h < t; h++){
        Topo.push_back(u = que[h]);
        for(i = first[u]; i; i = next[i])
            if(!--deg[e[i].v])
                que[t++] = e[i].v;
    }
}

int main(){
    scanf("%d%d", &V, &E);
    memset(deg, 0, sizeof deg);
    for(i = 1; i <= E; i++){
        scanf("%d%d", &u, &v);
        e[i] = edge(u, v);
        addedge(u, i);
        ++deg[v];
    }
    TopoSort();
    for(j = Topo.size() - 1; j >= 0; --j){
        dist[u = Topo[j]] = cnt = 0;
        con[u].set(u);
        for(i = first[u]; i; i = next[i]){
            pass[cnt++] = e[i].v;
            up(dist[u], dist[e[i].v] + 1);
        }
        sort(pass, pass + cnt, cmp);
        for(i = 0; i < cnt; i++){
            if(con[u].test(pass[i])) ++ans;
            con[u] |= con[pass[i]];
        }
    }
    printf("%d\n", ans);
    return 0;
}

坑

坑1：最大流无向图写习惯了，然后这道题也一上来也按照无向图的姿势，放了两个 addedge，结果样例都挂了。

坑2：还有遍历拓扑序的时候记得倒序，一开始~~傻逼一样~~写顺序，结果输出 0……

题目描述

输入格式

输出格式

题解

代码

坑