题意：给n个点，然后给出m个条件a、b，表示a可到达b，求最少需要建多少条有向边才能满足所有条件

思路：按所给的条件建有向图，可以发现，每一个联通块都是一个弱联通图，若一个m个点的联通块，如果没有环的话最少需要m-1条有向边，即连成一条链，若存在环，只需要m条边就可以连成一个强联通图，自然会满足联通块的所有条件，那么用拓扑判断有向环即可，注意建图的时候还是要建无向图，但是入度只记录条件给的边，因为如果建无向图，那么在dfs的时候不一定可以一次找到弱联通块所有的点，比如 1 2， 2 1这样的数据，所以建双向边，在每次dfs的时候把入度为0的点加入拓扑队列即可

AC代码：

#include "iostream"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#pragma comment(linker, "/STACK:102400000,102400000")#define ll long long#define endl ("\n")#define bug(x) cout<
     
      <<" "<<"UUUUU"<
      

Q;void add(int u, int v){ to[tot]=v; nex[tot]=head[u]; head[u]=tot++;}int dfs(int u){ int ret=1; vis[u]=1; if(in[u]==0){ Q.push(u); mk[u]=1; } for(int i=head[u]; i!=-1; i=nex[i]){ int v=to[i]; if(!vis[v]) ret+=dfs(v); } return ret;}bool topo(int u, int c){ int k=0; while(!Q.empty()){ int now=Q.front(); Q.pop(), k++; for(int i=head[now]; i!=-1; i=nex[i]){ int v=to[i]; in[v]--; if(!mk[v] && in[v]==0){ Q.push(v); mk[v]=1; } } } return k==c;}int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); mem(head,-1); cin>>n>>m; for(int _=1; _<=m; ++_){ int u, v; cin>>u>>v; add(u,v); add(v,u); in[v]++; } for(int i=1; i<=n; ++i){ if(!vis[i] && in[i]==0){ while(!Q.empty()) Q.pop(); int c=dfs(i); if(topo(i,c)) ans+=c-1; else ans+=c; } } for(int i=1; i<=n; ++i){ if(!vis[i]) ans++; } cout<

<