题目描述

Description

【故事背景】
还记得去年JYY所研究的强连通分量的问题吗？去年的题目里，JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的JYY，今年又琢磨起了“删边”的问题。
【问题描述】
对于一个N个点（每个点从1到N编号），M条边的有向图，JYY发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。
JYY想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？
为了简化一下大家的工作量，这次JYY保证他给定的有向图一定是一个有向无环图（JYY：大家经过去年的问题，都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以今年JYY就干脆简化一下大家的工作）。

Input

输入一行包含两个正整数N和M。
接下来M行，每行包含两个1到N之间的正整数x_i和y_i，表示图中存在一条从x_i到y_i的有向边。
输入数据保证，任意两点间只会有至多一条边存在。
N<=30,000,M<=100,000

Output

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

Sample Input

5 6
1 2
2 3
3 5
4 5
1 5
1 3

Sample Output

2

题目分析

先跑一波拓扑排序 拿出拓扑序后逆着枚举点 和与其联通的点 用bitset维护一下点与点之间的连通性
具体看代码吧

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;
int n,m;
int head[30100],net[100010],to[100010],ru[100010];
int tot;
bitset<30010> s[100010];
void add(int x,int y)
{
    net[++tot]=head[x];
    to[tot]=y;
    head[x]=tot;
}
int sta[30100];
int f[30100];
int cnt;
int num[100010];
int cmp(int j,int k)
{
    return num[j]<num[k];
}
void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++) if(!ru[i]) q.push(i),sta[++sta[0]]=i;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        num[nmp]=++cnt;
        for(int i=head[nmp];i;i=net[i])
            if(--ru[to[i]]==0) q.push(to[i]),sta[++sta[0]]=to[i];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        ru[y]++;
    }
    topsort();
    int ans=0;
    for(int i=sta[0];i;i--)
    {
        s[sta[i]][sta[i]]=1;
        f[0]=0;
        for(int j=head[sta[i]];j;j=net[j])
            f[++f[0]]=to[j];
        sort(f+1,f+f[0]+1,cmp);
        for(int j=1;j<=f[0];j++)
            if(s[sta[i]][f[j]]) ans++;
            else s[sta[i]]|=s[f[j]];
    }
    printf("%d",ans);
    return 0;
}