题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4635
题目描述：
给出一个有向图，问最大加入多少条边使原图还是不能强连通？
解题思路：
加入的边是最多的，那么肯定是强连通图减去一条边，可以先把图中的强连通分支找出来，然后把其中一个分支(包含x个点)独立出来，其余的点(包含n-x点)只和这x个点连通，但是不能双向连通。这样既可以得出图中一共有x*(x-1) + (n-x)*(n-x-1) + (n-1)*x条边，化简后可得n*(n-1) - x*(n-x),可知当x越小最后得到的图中边数越多。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 100005; 9 const int INF = 0x3f3f3f3f; 10 struct node 11 { 12 int to, next; 13 } edge[maxn]; 14 int head[maxn], low[maxn], dfn[maxn], stack[maxn], num[maxn]; 15 int instack[maxn], id[maxn], out[maxn], in[maxn], cnt, tot, top, ntime; 16 17 void init () 18 { 19 cnt = tot = top = ntime = 0; 20 memset (in, 0, sizeof(in)); 21 memset (id, 0, sizeof(id)); 22 memset (low, 0, sizeof(low)); 23 memset (dfn, 0, sizeof(dfn)); 24 memset (num, 0, sizeof(num)); 25 memset (out, 0, sizeof(out)); 26 memset (head, -1, sizeof(head)); 27 memset (stack, 0, sizeof(stack)); 28 memset (instack, 0, sizeof(instack)); 29 } 30 void Add (int from, int to) 31 { 32 edge[tot].to = to; 33 edge[tot].next = head[from]; 34 head[from] = tot ++; 35 } 36 void Tarjan (int u) 37 { 38 low[u] = dfn[u] = ++ ntime; 39 stack[top++] = u; 40 instack[u] = 1; 41 for (int i=head[u]; i!=-1; i=edge[i].next) 42 { 43 int v = edge[i].to; 44 if (!dfn[v]) 45 { 46 Tarjan(v); 47 low[u] = min (low[u], low[v]); 48 } 49 else if (instack[v]) 50 low[u] = min (low[u], dfn[v]); 51 } 52 if (dfn[u] == low[u]) 53 { 54 cnt ++; 55 while (1) 56 { 57 int v = stack[--top]; 58 instack[v] = 0; 59 num[cnt] ++; 60 id[v] = cnt; 61 if (v == u) 62 break; 63 } 64 } 65 } 66 int main () 67 { 68 int t, m, u, v, l = 0; 69 LL n; 70 scanf ("%d", &t); 71 while (t --) 72 { 73 init (); 74 scanf ("%lld %d", &n, &m); 75 for (int i=1; i<=m; i++) 76 { 77 scanf ("%d %d", &u, &v); 78 Add (u, v); 79 } 80 for (int i=1; i<=n; i++) 81 if (!dfn[i]) 82 Tarjan (i); 83 if (cnt == 1) 84 { 85 printf ("Case %d: -1 ", ++l); 86 continue; 87 } 88 for (int i=1; i<=n; i++) 89 for (int j=head[i]; j!=-1; j=edge[j].next) 90 { 91 u = id[i]; 92 v = id[edge[j].to]; 93 if (u != v) 94 { 95 in[u] ++; 96 out[v] ++; 97 } 98 } 99 LL x, ans = 0; 100 x = n * (n - 1) - m; 101 for (int i=1; i<=cnt; i++) 102 if (!in[i] || !out[i]) 103 ans = max (ans, x - num[i] * (n-num[i])); 104 printf ("Case %d: %lld ", ++l, ans); 105 } 106 return 0; 107 }