[JSOI2015]最小表示

链接：https://www.luogu.com.cn/problem/P6134

题目描述：给定一个\(DAG\)，求最多删多条边能使任意两点的连通性不会发生改变。

题解：手玩几组数据可以发现答案就是图中去掉边\((u,v)\)后\(u,v\)仍能连通的边的条数。然后这道题就变成了求对于每一条边，\((u,v)\)的路径条数是否大于等于\(2\)。

我们可以发现，如果将这道题稍微弱化以下，就变成了在\(DAG\)上给定\(q\)组点对\((u,v)\)，求\(u\)是否能到达\(v\)。我们知道这道题就是有向图可达性统计那一套，所以这道题至少要用到\(bitset\)。

判断大于\(2\)不怎么好直接做，那我们可以考虑维护两个\(bitset\):\(A\)与\(B\)，其中\(A\)维护路径条数大于等于\(1\)的,\(B\)维护路径条数大于等于\(2\)的，更新\(B\)时与\(A\)做一下与运算就可以求出\(B\)了。

#include<iostream>
#include<bitset>
#include<queue>
using namespace std;
struct node
{
	int v,nxt;
};
node edge[100001];
int n,m,cnt,len,in[100001],head[100001];
bitset<30001>A[30001];
bitset<30001>B[30001]; 
void add(int x,int y)
{
	edge[++len].v=y;
	edge[len].nxt=head[x];
	head[x]=len;
	return;
}
void top_sort()
{
	queue<int>q;
	for (int i=1;i<=n;++i)
		if (in[i]==0)
			q.push(i);
	int top;
	while (!q.empty())
	{
		top=q.front();
		q.pop();
		for (int i=head[top];i>0;i=edge[i].nxt)
		{
			in[edge[i].v]--;
			B[edge[i].v]|=(A[edge[i].v]&A[top]);
			A[edge[i].v]|=A[top];
			if (in[edge[i].v]==0)
				q.push(edge[i].v);
		}
	}
	return;
}
int main()
{
	int x,y;
	cin>>n>>m;
	for (int i=1;i<=m;++i)
	{
		cin>>x>>y;
		add(x,y);
		in[y]++;
	}
	for (int i=1;i<=n;++i)
		A[i][i]=1;
	top_sort();
	for (int i=1;i<=n;++i)
		for (int j=head[i];j>0;j=edge[j].nxt)
			if (B[edge[j].v][i]==1)
				cnt++;
	cout<<cnt<<endl;
	return 0; 
}