AtCoder292 E 思维

题意：

给定一副$n(n\le 3000)$个顶点，$m$条有向边的图，可以在图中添加有向边，求添加的最少边数，使得这副图满足：如果顶点$a$到顶点$b$有边，顶点$b$到$c$右有边，那么顶点$a$到顶点$c$也有边

Solution：

考虑一条单向链，按指向的方向按顺序是$A,B,C,D,...$

显然，$A\to B,B\to C$需要添加一条边$A\to C$，此时$A\to C,C\to D$需要添加$A\to D$。更一般的情况是，在从$A$出发能到达的顶点里，只有与$A$距离为1的不需要添加边，只需要和其他点建边即可，并查集不适合有向图，$O(n)$的搜索可以满足要求，每个顶点搜索一次，总复杂度$O(n^2)$

#include<iostream>
#include<vector>
#include<cstdlib>
#include<numeric>
#include<unistd.h>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<stack>
#include<utility>
#include<cctype>
#include<cassert>
#include<thread>
#include<bitset>
using namespace std;using ll=long long;
const int N=2e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;struct way {int to,next;
}edge[N<<1];
int cnt,head[N];void add(int u,int v) {edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}int n,m,dis[N],vis[N];int main() {#ifdef stdjudgefreopen("in.txt","r",stdin);auto TimeFlagFirst=clock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin>>n>>m;for(int i=1;i<=m;i++) {int u,v;cin>>u>>v;add(u,v);}int tot=0;queue<int>q;for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) vis[j]=false;while(!q.empty()) q.pop();q.push(i);while(!q.empty()) {int u=q.front(); q.pop();vis[u]=true;for(int j=head[u];j;j=edge[j].next) {int v=edge[j].to;if(vis[v]) continue;q.push(v);}}for(int j=1;j<=n;j++) {if(i!=j&&vis[j]) tot++;}for(int j=head[i];j;j=edge[j].next) tot--;}cout<<tot<<endl;#ifdef stdjudgefreopen("CON","r",stdin);std::cout<<std::endl<<"耗时:"<<std::clock()-TimeFlagFirst<<"ms"<<std::endl;std::cout<<std::flush;system("pause");#endifreturn 0;
}