[JSOI2015]最小表示（拓扑排序 + bitset维护）

链接：https://ac.nowcoder.com/acm/problem/20218
来源：牛客网

题目描述

【故事背景】还记得去年JYY所研究的强连通分量的问题吗？去年的题目里，JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的JYY，今年又琢磨起了“删边”的问题。

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

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

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

输入描述:

输入一行包含两个正整数N和M。

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

输入数据保证，任意两点间只会有至多一条边存在。 N ≤ 30,000,M ≤ 100,000

输出描述:

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

示例1

输入

复制

输出

复制

题意：

n 个点 m 条边的有向图，问最多可以删除多少条边使每个点的连通性不变。两点间最多只有一条边。

思路：

逆序遍历拓扑序列，保证每次加进的点都没有入度，设当前遍历到的点是 x ，然后对 x 可以直接到达的所有点按连通点数从大到小排序，记为 y ，如果 y 可以到的点 x 都已经可以到了，就把x -> y 删掉。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

vector<int>mp[N];
bitset<N>bit[N];
int d[N];   //d[i] : 点i连通的点数
int tp[N];  //拓扑序列
int in[N], n, m;

void topo() {
    int id = 0;
    queue<int>q;
    for(int i = 1; i <= n; ++i) {
        if(in[i] == 0)
            q.push(i);
    }
    while(!q.empty()) {
        int tmp = q.front();
        q.pop();
        tp[++id] = tmp;
        int siz = mp[tmp].size();
        for(int i = 0; i < siz; ++i) {
            int v = mp[tmp][i];
            in[v]--;
            if(in[v] == 0)
                q.push(v);
        }
    }
}

bool cmp(int x, int y) {
    return d[x] > d[y];
}

int main() {
    int u, v, y;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        in[i] = 0;
        mp[i].clear();
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        mp[u].push_back(v);
        in[v]++;
    }
    topo();
    int ans = 0;
    for(int i = n; i >= 1; --i) {
        int x = tp[i];
        bit[x].set(x);
        sort(mp[x].begin(), mp[x].end(), cmp);
        for(vector<int>::iterator it = mp[x].begin(); it != mp[x].end(); ++it) {
            y = *it;
            d[x] = max(d[x], d[y] + 1);
            if((bit[x] & bit[y]) == bit[y]) ++ans;
            else bit[x] |= bit[y];
        }
    }
    printf("%d\n", ans);
    return 0;
}