連邊的最后肯定是兩個集合x,y
x集合的每個元素，到y集合中的每個元素都是單向的邊
x集合，和y集合都是完全圖
設a為x集合的點的個數， b為y集合的
那么答案就是 a * b + a*(a-1) + b*(b-1) - m
n*n-a*b-n-m , 所以a*b盡量小， 即a和b的差值盡量大

縮點之后的點入度為0，或者出度為0才能成為x集合，y集合

1 #pragma warning(disable:4996) 2 #pragma comment(linker, "/STACK:1024000000,1024000000") 3 #include <iostream> 4 #include <stdio.h> 5 #include <string.h> 6 #include <vector> 7 #include <stack> 8 #include <queue> 9 #include <math.h> 10 #include <algorithm> 11 #include <map> 12 #include <set> 13 #include <functional> 14 using namespace std; 15 typedef __int64 LL; 16 const int N = 100000 + 10; 17 int dfn[N], low[N], sccno[N], cnt, dfs_clock, sum[N], in[N], out[N]; 18 vector<int> g[N]; 19 stack<int> st; 20 /* 21 22 23 */ 24 void init(int n) 25 { 26 cnt = dfs_clock = 0; 27 for (int i = 0;i <= n;++i) 28 { 29 30 in[i] = out[i] = dfn[i] = low[i] = sccno[i] = sum[i] = 0; 31 g[i].clear(); 32 } 33 } 34 void tarjan(int u, int fa) 35 { 36 dfn[u] = low[u] = ++dfs_clock; 37 st.push(u); 38 for (int i = 0; i<g[u].size(); ++i) 39 { 40 int v = g[u][i]; 41 if (dfn[v] == 0) 42 { 43 tarjan(v, u); 44 low[u] = min(low[u], low[v]); 45 } 46 else if (sccno[v] == 0)//因為有向圖存在橫插邊，不能用橫插邊來更新low[u] 47 { 48 low[u] = min(low[u], low[v]); 49 } 50 } 51 //同樣，因為強連通分量可以分布在根結點的兩個分支上，所以在遞歸返回的時候調用 52 if (low[u] == dfn[u]) 53 { 54 cnt++; 55 for (;;) 56 { 57 int x = st.top(); 58 st.pop(); 59 sccno[x] = cnt; 60 sum[cnt]++; 61 if (x == u) 62 break; 63 } 64 } 65 } 66 67 int main() 68 { 69 int t, n, m; 70 int u, v; 71 scanf("%d", &t); 72 for (int k = 1;k <= t;++k) 73 { 74 scanf("%d%d", &n, &m); 75 init(n); 76 for (int i = 1;i <= m;++i) 77 { 78 scanf("%d%d", &u, &v); 79 g[u].push_back(v); 80 81 } 82 for (int i = 1;i <= n;++i) 83 if (dfn[i] == 0) 84 tarjan(i, -1); 85 for (int u = 1;u <= n;++u) 86 { 87 for (int i = 0;i < g[u].size(); ++i) 88 { 89 int v = g[u][i]; 90 if (sccno[u] != sccno[v]) 91 { 92 in[sccno[v]]++; 93 out[sccno[u]]++; 94 } 95 } 96 } 97 if (cnt == 1) 98 { 99 printf("Case %d: -1\n", k); 100 continue; 101 } 102 LL ans = 0; 103 for (int i = 1;i <= cnt;++i) 104 { 105 if (!in[i] || !out[i])//出度為0或者入度為0的連通分量才能成為一個集合，剩余的成為另一個集合 106 { 107 LL a = sum[i]; 108 LL b = n - a; 109 ans = max(ans, n*n - a*b - n - m); 110 } 111 } 112 printf("Case %d: %I64d\n", k, ans); 113 } 114 return 0; 115 }

?

轉載于:https://www.cnblogs.com/justPassBy/p/4798367.html

總結

以上是生活随笔為你收集整理的hdu4635（最多加多少边，使得有向图不是强连通图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。