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
Solution
看的题解...感觉bitset这个东西就很少在我脑子里存在过...
因为是个dag考虑先拓扑一遍把拓扑序处理出来，一条边((u,v))可删当且仅当存在点(x)，有路径(u->x)和(x->v)。那么很容易看出删边是相互独立的。接下来就不会了...
题解是用的bitset维护点对之间的联通。按拓扑序逆序处理，每个点的出边所连的点的拓扑序肯定大于它，且拓扑序更小的对答案的贡献更大（因为拓扑序越小，可达点就越多），所以在处理之前把每个点的出边按(v)的拓扑序升序排序，那么每次对于边((u,v))，如果(u)已经可达(v)那么直接删除该边，否则给当前点(u)的可达集合或上(v)和(v)的可达集合。复杂度是(O(frac{nm}{w}))
#include <bits/stdc++.h>
using namespace std;
namespace io {
char buf[1<<21], *p1 = buf, *p2 = buf;
inline char gc() {
if(p1 != p2) return *p1++;
p1 = buf;
p2 = p1 + fread(buf, 1, 1 << 21, stdin);
return p1 == p2 ? EOF : *p1++;
}
#define G gc
#ifndef ONLINE_JUDGE
#undef G
#define G getchar
#endif
template<class I>
inline void read(I &x) {
x = 0; I f = 1; char c = G();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = G(); }
while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = G(); }
x *= f;
}
template<class I>
inline void write(I x) {
if(x == 0) {putchar('0'); return;}
I tmp = x > 0 ? x : -x;
if(x < 0) putchar('-');
int cnt = 0;
while(tmp > 0) {
buf[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while(cnt > 0) putchar(buf[--cnt]);
}
#define in(x) read(x)
#define outn(x) write(x), putchar('
')
#define out(x) write(x), putchar(' ')
#undef G
} using namespace io;
#define ll long long
const int N = 30010;
bitset<N>f[N];
vector<int> G[N];
int du[N], n, m, id[N], q[N], w[N];
void topsort() {
int l = 1, r = 1, tim = 0;
for(int i = 1; i <= n; ++i) if(!du[i]) q[r++] = i;
while(l < r) {
int u = q[l++];
id[u] = ++tim;
w[tim] = u;
for(int i = 0, len = G[u].size(); i < len; ++i) {
int v = G[u][i];
du[v]--;
if(!du[v]) q[r++] = v;
}
}
}
bool cmp(int a, int b) {
return id[a] < id[b];
}
int main() {
read(n); read(m);
for(int i = 1, u, v; i <= m; ++i) {
read(u); read(v);
G[u].push_back(v);
du[v]++;
}
topsort();
int ans = 0;
for(int i = n; i; --i) sort(G[i].begin(),G[i].end(),cmp);
for(int i = n; i; --i) {
int u = w[i];
for(int j = 0, len = G[u].size(); j < len; ++j) {
int v = G[u][j];
if(f[u].test(id[v])) ++ans;
else {
f[u][id[v]] = 1;
f[u] |= f[v];
}
}
}
outn(ans);
}