本文主要是介绍hdu-4635-Strongly connected-强连通分量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你一个有向图，问你最多能添加多少条边使得这个图依然不是强联通的。
做法：
1，求出图中的所有强连通分量
2，把上述的强连通分量缩成一个点。
3，问题现在变成问一个完全图，最少需要去除多少条边使得这个图不强联通，
那么肯定是去除所有强联通分量中含有点数最少的点的所有进边。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stack>
#include<vector>
using namespace std;
#define maxn 100005
#define mem(a,b) memset(a,b,sizeof(a));
vector<int>q[maxn];
stack<int>qq;
int times;
int nums;
int num[maxn];
int dnf[maxn];
int low[maxn];
int out[maxn];
int in[maxn];
int sum[maxn];
int instack[maxn];
void tarjan(int x)
{dnf[x]=low[x]=times++;instack[x]=1;qq.push(x);int i;for(i=0;i<q[x].size();i++){int y=q[x][i];if(!dnf[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(instack[y]){low[x]=min(low[x],dnf[y]);}}if(dnf[x]==low[x]){int y=-1;while(y!=x){y=qq.top();qq.pop();num[y]=nums;instack[y]=0;sum[nums]++;}nums++;}//cout<<x<<" "<<low[x]<<" "<<dnf[x]<<endl;
}
int main()
{// freopen("1004.in","r",stdin);int T,cas,i,j,n,m;cin>>T;for(cas=1;cas<=T;cas++){cin>>n>>m;for(i=1;i<=n;i++)q[i].clear();while(!qq.empty())qq.pop();mem(in,0);mem(out,0);mem(dnf,0);mem(low,0);mem(num,0);mem(sum,0);mem(instack,0);nums=0;int x,y;for(i=0;i<m;i++){scanf("%d%d",&x,&y);q[x].push_back(y);}for(i=1;i<=n;i++)if(!dnf[i])tarjan(i);if(nums==1){printf("Case %d: -1\n",cas);continue;}for(i=1;i<=n;i++){for(j=0;j<q[i].size();j++){if(num[i]!=num[q[i][j]]){out[num[i]]++;in[num[q[i][j]]]++;}}}int maxx=maxn;for(i=0;i<nums;i++){if(in[i]==0||out[i]==0){if(sum[i]<maxx)maxx=sum[i];}}__int64 ss;ss=0;ss =(__int64)n*(n-1);ss-=(__int64)m;ss-=(__int64)maxx*(n-maxx);printf("Case %d: %I64d\n",cas,ss);}return 0;
}这篇关于hdu-4635-Strongly connected-强连通分量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
