洛谷P6134 [JSOI2015]最小表示题解

题目链接：P6134 [JSOI2015]最小表示

题意：

对于一个 $N$ 个点（每个点从 $1$ 到 $N$ 编号），$M$ 条边的有向图，cxy 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。

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

为了简化一下大家的工作量，这次 cxy 保证他给定的有向图一定是一个有向无环图（cxy：大家都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以就干脆简化一下大家的工作）。

输入格式：

第一行包含两个正整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个 $1$ 到 $N$ 之间的正整数 $x_i$ 和 $y_i$，表示图中存在一条从 $x_i$ 到 $y_i$ 的有向边。

输入数据保证，任意两点间只会有至多一条边存在。

输出格式：

输出一行包含一个整数，表示cxy最多可以删掉的边数。

数据范围：

对于 $100\%$ 的数据，$1 \leq N\leq 3\times 10^4$，$0 \leq M\leq 10^5$。

不难发现每对节点保留其最长的路径一定可以得到最优解。

证明：

~~感性理解的话~~，是因为保留这些边的过程最大化了边的利用价值。

考虑原图的一个拓扑序，显然它构成一棵树，且边均由子结点指向父结点

当然拓扑序不能反映原图的连通性，实际上这棵树上还有一些“返祖边”

这里“返祖边”类似于dfs树的返祖边，由某个结点指向它的某个祖先或祖先的兄弟。

如果 $u$ 为叶子结点，显然仅留“返祖边”是最优的。

如果 $u$ 不为叶子结点，我们首先会尝试让 $u$ 的儿子连上 $u$ ，然后尝试 $u$ 的孙子…

不难发现这样一定是优的，因为连深度较大的结点只会让答案增大。

至此，我们证明了算法的正确性。$\square$

考虑用 $\mathtt{bitset}$ 维护结点的连通性。

设 $u$ 向 $v$ 连了一条有向边。

我们用 link[u][v] 表示 $u$ 与 $v$ 连通
因为 $v$ 能到达的结点 $u$ 也能到达，因此我们可以直接 link[u] |= link[v]

时间复杂度 $\mathcal{O}\left(\frac{n^2\log n}{32}\right)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e4+15))
#define M ((int)(1e5+15))

bitset<N> link[N];
int n,m,pos=1,head[N],to[N],in[N],id[N],dfn[N];
struct Edge{int u,v,next;} e[M];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
int topo()
{
    int res=0,tim=0; queue<int> q;
    for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        id[++tim] = u; dfn[u] = tim;
        for(int i=head[u]; i; i=e[i].next)
            if(!(--in[e[i].v])) q.push(e[i].v);
    }
    for(int k=n; k>=1; k--)
    {
        int u = id[k], cnt=0; link[u][u] = 1;
        for(int i=head[u]; i; i=e[i].next)
            to[++cnt] = e[i].v;
        sort(to+1, to+1+cnt, [](int a,int b) { return dfn[a] < dfn[b]; });
        for(int i=1; i<=cnt; i++)
            if(link[u][to[i]]) ++res;
            else link[u] |= link[to[i]];
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        addEdge(u,v); ++in[v];
    }
    cout << topo() << '\n';
    return 0;
}