P6134 [JSOI2015]最小表示 题解

· · 题解

对于每一条边 (u,v)，如果从 u 到 v 仅存在这条路径，那么这条边一定要保存，否则一定可以删除，因为若存在另一条从 u 到 v 的路线，那么一定存在一个不同于 u,v 的点 x ，可以使 u 到 x, x 到 v，那么显然边 (u,v) 是可以删除的。

那么接下来就要想办法对每条边判断是否存在点 x ，我们可以对每个点，处理出这个点可以到的点，以及有哪些点可以到这个点，那么就是可达性统计了。

接下来就是对 u 和 v，看 u 可到达的点和可以到 v 的点是否有相同的就可以了。

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
    x=0;bool t=false;char c=getchar();
    while(c<'0'||c>'9')c=='-'?t=1:0,c=getchar();
    while(c>='0'&&c<='9')x=x*10+(c&15),c=getchar();
    t?x=-x:x;
}
const int N=3e4+10,M=1e5+10;
vector<int>e[N];
vector<int>back[N];
int in[N],u[M],v[M];
bitset<N>to[N],cm[N];//两个点集to和come
int tupo[N],cnt=0,n,m;
void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;++i)
        if(!in[i])
            q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        tupo[++cnt]=x;
        for(int y:e[x])
        {
            in[y]--;
            if(!in[y])
                q.push(y);
        }
    }
}
int main()
{
    read(n);read(m);
    for(int i=1;i<=m;++i)
    {
        read(u[i]);read(v[i]);
        e[u[i]].push_back(v[i]);
        back[v[i]].push_back(u[i]);
        in[v[i]]++;
    }
    topsort();
    for(int i=n;i;--i)
    {
        int x=tupo[i];
        for(int y:e[x])
        {
            to[x][y]=1;
            to[x]|=to[y];
        }
    }
    for(int i=1;i<=n;++i)
    {
        int x=tupo[i];
        for(int y:back[x])
        {
            cm[x][y]=1;
            cm[x]|=cm[y];
        }
    }
    int ans=0;
    for(int i=1;i<=m;++i)   
        if((to[u[i]]&cm[v[i]])!=0)
            ans++;
    printf("%d",ans);
    return 0;
}