P6134 最小表示

DAG 传递约简中的两个拓扑顺序

问题

P6134 [JSOI2015] 最小表示
给定一张没有重边的 DAG。可以删除一部分边，但删除后任意两点之间的可达关系必须与原图完全相同，求最多能够删除多少条边，也就是统计有多少条直接边已经能被其他有向路径替代。

数据规模：$1\le n\le3\times10^4$，$0\le m\le10^5$。

考虑什么样的边是可以删除的，对于样例来说，我们能发现一点规律，比如：

1 -> 2 -> 3 -> 5
|    |         ^
+--> 3         |
+------------> 5

中，其实 1->3 和 1->5 这两条边就可以删掉。

我最初猜测可以“保留最长的路径，删掉其余路径上的直接边”。这个说法并不严谨，因为目标不是选出某一条最长路；真正成立的局部判据是，一条直接边是否已经能被另一条长度至少为二的有向路径替代。

也就是说，对于 $(u, v)$ 来说，如果存在 $u \to x \to v$，那么这条边就可以删除。

于是问题就转化为了可达性统计类问题，为了记录每个点最终可以到达哪些点，我们对反图进行拓扑排序，并使用 bitset来优化，最后在正图上再判断一遍即可。

当然不用真的建反图，我们可以在正图上跑拓扑，然后对正拓扑序取反即可。

最后对每一个点的出边，都按照目标点的正拓扑序升序排序，若处理边 $u\to v$ 时已经知道 $u$ 可以通过其他后继到达 $v$，这条边就是冗余边。

顺序

这里有两个顺序，点的可达统计要按照逆拓扑序处理，保证计算 $u$ 时每个后继 $v$ 的可达集合已经完整；同一个点的出边必须按终点的正拓扑序处理，保证若 $u\to a\to\cdots\to b$，一定先借助 $a$ 扩展可达集合，再判断直接边 $u\to b$。

使用 bitset 按机器字并行维护可达集合，主要复杂度为 $O(mn/w)$，另外需要 $O(n+m)$ 的拓扑排序和邻接表排序开销。

▶

AC 代码

vector<int> adj[maxn];
bitset<maxn> reach[maxn];

int pos[maxn]; 
// pos[u] 表示 u 在拓扑序中的位置，用于给出边排序
int ind[maxn];

bool cmp( int x, int y ) {
    return pos[x] < pos[y];
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back( v );
        ind[v] ++;
    }

    queue<int> q;
    for( int i = 1; i <= n; ++ i ) {
        if( !ind[i] ) q.push( i );
    }

    vector<int> ord; // 拓扑序
    ord.push_back( 0 );
    while( !q.empty( ) ) {
        int u = q.front( ); q.pop( );
        ord.push_back( u );
        for( int v : adj[u] ) {
            if( --ind[v] == 0 ) q.push( v );
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        pos[ord[i]] = i;
    }

    for( int i = 1; i <= n; ++ i ) {
        sort( adj[i].begin( ), adj[i].end( ), cmp );
    }

    int ans = 0;
    for( int i = n; i >= 1; -- i ) {
        int u = ord[i];
        for( int v : adj[u] ) {
            if( reach[u][v] ) {
                ans ++;
                continue;
            }
            reach[u] |= reach[v];
            reach[u].set( v );
        }
    }
    printf( "%d\n", ans );
}