题目就是告诉你有m条边是从u通向v的,问你至少添加多少条边之后,能形成一个强连通。模版题。
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #include <stack> #include <vector> #define LL long long #define M 20005 using namespace std; vector<int> G[M]; int dfn[M],low[M],sccno[M],scc_cnt,index; stack<int> s; void Tarjan(int u) { dfn[u]=low[u]=++index; s.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) { scc_cnt++; for(;;) { int x=s.top(); s.pop(); sccno[x]=scc_cnt; if(x==u) break; } } } void find_scc(int n) { index=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); for(int i=0;i<n;i++) if(!dfn[i]) Tarjan(i); } int main() { int n,m; int in0[M],out0[M]; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) G[i].clear(); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); u--,v--; G[u].push_back(v); } find_scc(n); for(int i=1;i<=scc_cnt;i++) in0[i]=out0[i]=1; for(int u=0;u<n;u++) { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(sccno[u]!=sccno[v]) in0[sccno[v]]=out0[sccno[u]]=0; } } int a=0,b=0; for(int i=1;i<=scc_cnt;i++) { if(in0[i]) a++; if(out0[i]) b++; } int ans=max(a,b); if(scc_cnt==1) ans=0; printf("%d\n",ans); } return 0; }