题意：给一个n×n矩阵，mp[i][j]=1代表i到j之间有一条i指向j的有向边，同一个强联通分量之间可以随便加边，不同强连通分量之间只能有单向连边，问在现有的图的基础上，最多能加多少条边。
题解：tarjan缩点时记录每个连通分量包含的点的数量。ans一开始等于-tot，因为一定会减去现有的边。然后从第一个连通分量开始遍历，用pre记录连通分量点数量的前缀和，每一次，ans+=(num[i]-1)num[i]（同一个连通分量之间的点可以随意连边），ans+=prenum[i]（不同连通分量之间只能单向连边）。
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <vector>#include <queue>using namespace std;typedef long long ll;const int maxn = 2505;int n,m;int head[maxn],tot;int dfn[maxn],low[maxn],Stack[maxn],belong[maxn],num[maxn],top,scc,cnt;bool vis[maxn];struct node{int to,next;}a[maxn*maxn];void add(int x,int y){a[tot].to = y;a[tot].next = head[x];head[x] = tot++;}void tarjan(int u){int v;low[u] = dfn[u] = ++cnt;vis[u] = true;Stack[top++] = u;for(int i=head[u]; i!=-1; i=a[i].next){v = a[i].to;if(!dfn[v]){tarjan(v);low[u] = min(low[u],low[v]);}else{if(vis[v])low[u] = min(low[u],low[v]);}}if(low[u] == dfn[u]){scc++;do{v = Stack[--top];vis[v] = false;belong[v] = scc;num[scc]++;}while(v != u);}}void solve(){memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));top = cnt = scc = 0;for(int i=1; i<=n; i++){if(!dfn[i])tarjan(i);}}int main(){scanf("%d",&n);memset(head,-1,sizeof(head));for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){int k;scanf("%d",&k);if(k)add(i,j);}}solve();int ans = -tot,pre = 0;for(int i=1; i<=scc; i++){ans += (num[i]-1)*num[i];ans += pre*num[i];pre += num[i];}printf("%d",ans);}
如果觉得《给有向图加边》对你有帮助，请点赞、收藏，并留下你的观点哦！
