Strongly connected HDU - 4635(tarjan+强连通分量）
題意：
給一個簡單有向圖，讓你加最多的邊，使他還是一個簡單有向圖。
題目：
Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can add that the graph is still a simple directed graph. Also, after you add these edges, this graph must NOT be strongly connected.
A simple directed graph is a directed graph having no multiple edges or graph loops.
A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point.
Input
The first line of date is an integer T, which is the number of the text cases.
Then T cases follow, each case starts of two numbers N and M, 1<=N<=100000, 1<=M<=100000, representing the number of nodes and the number of edges, then M lines follow. Each line contains two integers x and y, means that there is a edge from x to y.
Output
For each case, you should output the maximum number of the edges you can add.
If the original graph is strongly connected, just output -1.
Sample Input
3
3 3
1 2
2 3
3 1
3 3
1 2
2 3
1 3
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Sample Output
Case 1: -1
Case 2: 1
Case 3: 15
分析：
1.首先要把這個圖變成一個完全圖，然后減去最初的m條邊。
2.因為要求加入的邊最大化，你需要強聯通縮點，把入度為0或者出度為0的內含節點最少的聯通塊找出來，然后再減去最小聯通塊內的點與其他點的連接邊就可以了。（減去的最少，剩余的也越多）
3.考慮當只有一個連通圖時，不滿足，輸出-1；
AC代碼：
#include<stdio.h> #include<string.h> #include<vector> #include<iostream> #include<stack> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; const int M=1e5+10; int t,n,m,u,v,tot,k,mi,Case; vector<int>ve[M]; int dfn[M],low[M],co[M],out[M],in[M],num[M]; stack<int>st; void tarjan(int x) {dfn[x]=low[x]=++tot;st.push(x);//入棧for(int i=0; i<ve[x].size(); i++){int y=ve[x][i];if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(!co[y])low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x])///某個節點回溯之后的low【u】值還是==dfn【u】的值，那么這個節點無疑就是一個關鍵節點（為強連通分量的一個頂點。）{k++;/**縮點，將連通分量縮成一個點，建入新樹中*/while(1){int a=st.top();st.pop();co[a]=k;/*看做建了一個新樹，只有用強連通分量的頂點建入樹中*/num[k]++;/*記錄某連通分量內有多少個點*/if(a==x)//（遍歷該連通分量內有多少個點【在a前的點，均為一個連通分量】）break;}} } int main() {scanf("%d",&t);Case=0;while(t--){tot=k=0;/**初始化*/memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(co,0,sizeof(co));memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(num,0,sizeof(num));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)ve[i].clear();for(int i=0; i<m; i++){scanf("%d%d",&u,&v);ve[u].push_back(v);}for(int i=1; i<=n; i++)if(!dfn[i])tarjan(i);mi=inf;for(int i=1; i<=n; i++)for(int j=0; j<ve[i].size(); j++)if(co[i]!=co[ve[i][j]])out[co[i]]++,in[co[ve[i][j]]]++;for(int i=1; i<=k; i++)if(!in[i]||!out[i])mi=min(mi,num[i]);printf("Case %d: ",++Case);if(k==1)printf("-1\n");elseprintf("%d\n",n*(n-1)-m-mi*(n-mi));}return 0; } /**想法一： 找出強聯通塊，計算每個連通塊內的點數。將點數最少的那個連通塊單獨拿出來， 其余的連通塊合并成一個連通分量。 那么假設第一個連通塊的 點數是 x 第二個連通塊的點數是 y 一個【強】連通圖最多（每兩個點之間，至少存在一條課互相到達的路徑）的邊數為n*（n-1） 一個連通圖的邊數至少為n*（n-1）- x*y + 1 則非連通圖最多的邊數為n*（n-1）- x*y 即 x*（x-1）+ y*（y-1）+ x*y 因為原圖中已經有m條邊 所以最多加 x*（x-1）+ y*（y-1）+ x*y - m 條邊 這里最少點數的強聯通分量要滿足一個條件，就是出度或者入度為 0才行，不然是不滿足的。 二： 縮點后 這其實就相當于一個完全圖至少減去多少條邊，使之變成非強連通圖 肯定減去連通分量里點最少的那個了*/備戰ing，題目分析簡略，見諒，轉載請注明出處。。。。。
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的Strongly connected HDU - 4635(tarjan+强连通分量）的全部內容，希望文章能夠幫你解決所遇到的問題。
