题目地址:HDU 2767 题意：给一张有向图，求最少加几条边使这个图强连通。 思路：先求这张图的强连通分量，如果为1，则输出0（证明该图不需要加边已经是强连通的了)，，否则缩点。遍历原图的所有边，如果2个点在不同的强连通分量里面，建边，构成一张新图。统计新图中点的入度和出度，取入度等于0和出度等于0的最大值(因为求强连通缩点后，整张图就变成了一个无回路的有向图，要使之强连通，只需要将入度=0和出度=0的点加边即可，要保证加边后没有入度和出度为0的点，所以取两者最大值）
*;LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;const int maxn=21010;int head[maxn],dfn[maxn],low[maxn],belong[maxn],stak[maxn],instack[maxn];int in[maxn],out[maxn];int incnt,outcnt;int cnt,index,top,ans;struct node {int u, v, next;} edge[maxn*3];void add(int u, int v) {edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void Init() {memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(instack,0,sizeof(instack));cnt=index=top=ans=0;memset(in,0,sizeof(in));memset(out,0,sizeof(out));incnt=outcnt=0;}void tarjan(int u) {dfn[u]=low[u]=++index;stak[++top]=u;instack[u]=1;for(int i=head[u]; i!=-1; i=edge[i].next) {int v=edge[i].v;if(!dfn[v]) {tarjan(v);low[u]=min(low[u],low[v]);} else if(instack[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]) {ans++;while(1) {int v=stak[top–];instack[v]=0;belong[v]=ans;if(u==v) break;}}}int main() {int T, n, m,i, j;int u,v;scanf(“%d”,&T);while(T–) {scanf(“%d%d”,&n,&m);Init();while(m–) {scanf(“%d%d”,&u,&v);add(u,v);}for(i=1; i<=n; i++) {if(!dfn[i])tarjan(i);}if(ans==1) {printf(“0\n”);continue ;}for(i=1; i<=n; i++) {for(j=head[i]; j!=-1; j=edge[j].next) {int v=edge[j].v;if(belong[v]!=belong[i]) {in[belong[v]]++;out[belong[i]]++;}}}for(i=1; i<=ans; i++) {if(!in[i])incnt++;if(!out[i])outcnt++;}printf(“%d\n”,max(incnt,outcnt));}return 0;}*
一个人的天地是冷得连呼吸都会寂寞的颤栗，而麻烦，
