526互联

AtCoder Beginner Contest 292 E - Transitivity

发布时间 2023-09-01 13:44:12作者: 无上大宗师

E - Transitivity

原题链接


题意：对于一个有向图，进行加边操作，使最终任意的个点具有传递效果，即若a到b有边，b到c有边，那么a到c也要有边，问最少需要进行多少次操作，使得每个节点所能到达的地方都有直接的边，也就是最短距离为1


思路：怎么加边才是最优的，举个例子a->b->c->d->e 对于a点到其他点的距离大于等于2时，就必须要加边。
因此，最少的操作数，即每个点到其他点的距离是大于等于2的节点对的数目和

#include <bits/stdc++.h>
using namespace std;
const int N = 2010,M=N<<1;
int e[M],ne[M],h[N],idx;
int n,m;
int ans;
int d[M];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int S)
{
	memset(d,-1,sizeof(d));
	queue<int> q;
	q.push(S);
	d[S]=0;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		if(d[u]>=2) ans++;
		for(int i=h[u];~i;i=ne[i])
		{
			int v=e[i];
			if(d[v]==-1)
			{
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
}
int main()
{
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)
	{
		bfs(i);
	}
	cout<<ans<<'\n';
}