1 /* 2 題意：給定一個連通的無向圖G，至少要添加幾條邊，才能使其變為強連通圖（指的是邊強聯通）。 3 思路：利用tarjan算法找出所有的雙聯通分量！然后根據low[]值的不同將雙聯通分量 4 進行縮點，最后圖形會變成一棵樹！也就是添加至少多少條邊使一棵樹變成強聯通圖！ 5
6 知識點：若要使得任意一棵樹，在增加若干條邊后，變成一個雙連通圖，那么 7 至少增加的邊數 =（ 這棵樹總度數為1的結點數 + 1 ）/ 2 8 9 */ 10 #include<iostream> 11 #include<cstring> 12 #include<cstdio> 13 #include<algorithm> 14 #include<vector> 15 #define N 1005 16 using namespace std; 17 vector<int>g[N]; 18 int low[N], pre[N]; 19 int deg[N]; 20 int n, m; 21 int cnt; 22 int dfsClock; 23 void dfs(int u, int fa){ 24 low[u]=pre[u]=++dfsClock; 25 int len=g[u].size(); 26 for(int i=0; i<len; ++i){ 27 int v=g[u][i]; 28 if(!pre[v]){ 29 dfs(v, u); 30 low[u]=min(low[u], low[v]); 31 } 32 else if(pre[v] < pre[u] && fa!=v) 33 low[u]=min(pre[v], low[u]); 34 } 35 } 36 37 int main(){ 38 while(scanf("%d%d", &n, &m)!=EOF){ 39 memset(pre, 0, sizeof(pre)); 40 memset(deg, 0, sizeof(deg)); 41 while(m--){ 42 int u, v; 43 scanf("%d%d", &u, &v); 44 g[u].push_back(v); 45 g[v].push_back(u); 46 } 47 cnt=0; 48 dfsClock=0; 49 dfs(1, -1); 50 for(int i=1; i<=n; ++i){ 51 int len=g[i].size(); 52 for(int j=0; j<len; ++j){ 53 int v=g[i][j]; 54 if(low[i]!=low[v]) 55 ++deg[low[i]]; 56 } 57 } 58 for(int i=1; i<=n; ++i) 59 if(deg[i]==1) 60 ++cnt; 61 printf("%d\n", (cnt+1)/2); 62 for(int i=1; i<=n; ++i) 63 g[i].clear(); 64 } 65 return 0; 66 }
?
)
; 很牛逼)
)
)
)
)
