n個點,m條邊的有向圖,求最多能增加多少條邊,原圖任然不是強連通圖。
將問題轉化為,n個點的完全圖,共有n*(n-1)條邊,除去原有的m條邊,最少刪多少條邊,使得該圖不是強連通圖?
求出scc后縮點得到scc圖,對于一個scc點,如果他的入度為0,那么只需在完全圖中,刪去所有指向該強連通分量的邊就行了,對于出度為0的scc點也是如此。而要求最大的可加邊數,只需求出入度或者出度為0的點權最小的那個scc就行,答案便是n*(n-1) - m - sum[_scc] * (n-sum[_scc]) 。
?
#include<iostream> #include<algorithm> #include<vector> #include<string> #include<queue> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<fstream> #include<sstream> #include<map> #include<set> #define FF(i, a, b) for(int i=a; i<b; i++) #define FD(i, a, b) for(int i=a; i>=b; i--) #define REP(i, n) for(int i=0; i<n; i++) #define CLR(a, b) memset(a, b, sizeof(a)) #define LL long long #define PB push_back #define debug puts("**debug**") using namespace std; const int maxn = 100001; int n, m, u, v; int pre[maxn], low[maxn], dfs_clock, scc_cnt, sccno[maxn], in[maxn], out[maxn], sum[maxn]; vector<int> G[maxn]; stack<int> S; void dfs(int u) { pre[u] = low[u] = ++dfs_clock; S.push(u); REP(i, G[u].size()) { int v = G[u][i]; if(!pre[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if(!sccno[v]) low[u] = min(low[u], pre[v]); } if(low[u] == pre[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x == u) break; } } } void find_scc() { dfs_clock = scc_cnt = 0; CLR(pre, 0); CLR(sccno, 0); CLR(in, 0); CLR(out, 0); CLR(sum, 0); FF(i, 1, n+1) if(!pre[i]) dfs(i); } int main() { int T; scanf("%d", &T); FF(kase, 1, T+1) { scanf("%d%d", &n, &m); FF(i, 1, n+1) G[i].clear(); REP(i, m) { scanf("%d%d", &u, &v); G[u].PB(v); } find_scc(); printf("Case %d: ", kase); if(scc_cnt == 1) { puts("-1"); continue; } LL ans = n*(n-1) - m; FF(u, 1, n+1) { sum[sccno[u]]++; REP(i, G[u].size()) { int v = G[u][i]; if(sccno[u] != sccno[v]) out[sccno[u]]++, in[sccno[v]]++; } } int tmp = 1e9; FF(i, 1, scc_cnt+1) if(in[i] == 0 || out[i] == 0) tmp = min(tmp, sum[i]); ans -= tmp*(n-tmp); printf("%lld\n", ans); } return 0; }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
