kuangbin專題 專題九 連通圖 Warm up HDU - 4612

題目鏈接：https://vjudge.net/problem/HDU-4612

題目：一個大地圖，給定若干個連通圖，每個連通圖中有若干個橋，你可以在任意某個連通圖的

任意兩個點添加一條邊，問，添加一條邊后，大地圖中最少剩下幾個橋，

思路：tarjan縮點，重構圖，對每個新圖跑兩次dfs求出樹的直徑，取所有新圖的直徑max，

答案就是  大地圖總橋數 - max(樹的直徑)，

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <vector>
  6 using namespace std;
  7 #define pb push_back
  8 
  9 const int N = (int)2e5+10;
 10 const int M = (int)1e6+10;
 11 int n,m,bridge,tot,tim,top,scc;
 12 int head[N],dfn[N],low[N],s[N],scc_no[N],vis[N];
 13 struct node{
 14     int to;
 15     int nxt;
 16 }e[M << 1];
 17 vector<int> g[N];//新圖
 18 vector<int> poi;//存單個連通圖包含的點
 19 
 20 void init(){
 21     for(int i = 0; i <= n; ++i){
 22         head[i] = -1;
 23         dfn[i] = 0;
 24         g[i].clear();
 25     }
 26     bridge = tot = tim = top = scc = 0;
 27 }
 28 
 29 inline void add(int u,int v){
 30     e[tot].to = v;
 31     e[tot].nxt = head[u];
 32     head[u] = tot++;
 33 }
 34 
 35 //tarjan縮點
 36 void tarjan(int now,int pre){
 37     poi.pb(now);//存下這個連通圖包含的點
 38     dfn[now] = low[now] = ++tim;
 39     s[top++] = now;
 40     int to,pre_cnt = 0;
 41     for(int o = head[now]; ~o; o = e[o].nxt){
 42         to = e[o].to;
 43         if(to == pre && pre_cnt == 0) { pre_cnt = 1; continue; }
 44         if(!dfn[to]){
 45             tarjan(to,now);
 46             low[now] = min(low[now],low[to]);
 47             if(dfn[now] < low[to]) ++bridge;
 48         }else low[now] = min(low[now],dfn[to]);
 49     }
 50 
 51     if(dfn[now] == low[now]){
 52         int x;
 53         ++scc;
 54         do{
 55             x = s[--top];
 56             scc_no[x] = scc;
 57         }while(now != x);
 58     }
 59 }
 60 
 61 //對poi中的那些點新建一個圖
 62 void rebuild(){
 63     int to,now;
 64     for(int i = 0; i < (int)poi.size(); ++i){
 65         now = poi[i];
 66         for(int o = head[now]; ~o; o = e[o].nxt){
 67            to = e[o].to;
 68            if(scc_no[now] == scc_no[to]) continue;
 69            g[scc_no[now]].pb(scc_no[to]);  g[scc_no[to]].pb(scc_no[now]);
 70         }
 71     }
 72 }
 73 
 74 void dfs(int now,int pre,int deep){
 75     vis[now] = deep;
 76     int to;
 77     for(int i = 0; i < (int)g[now].size(); ++i){
 78         to = g[now][i];
 79         if(to == pre || to == now || vis[to]) continue;
 80         dfs(to,now,deep+1);
 81     }
 82 }
 83 
 84 void test01(){
 85     for(int i = 1; i <= n; ++i)
 86         printf("%d 屬于scc = %d\n",i,scc_no[i]);
 87 }
 88 
 89 
 90 void solve(){
 91 
 92     int max_deep = 0,_deep = 0;
 93     int u;
 94     for(int i = 1; i <= n; ++i){
 95         if(!dfn[i]){
 96             poi.clear();//清空上個連通圖中的點
 97             tarjan(i,i);
 98             rebuild();//poi中的點重建圖
 99             dfs(poi[0],poi[0],1);
100             _deep = 0;
101             for(int i = 0; i < poi.size(); ++i){
102                 if(_deep < vis[poi[i]]){ _deep = vis[poi[i]]; u = poi[i]; }
103                 vis[poi[i]] = 0; //這里別忘了初始化  不然下次dfs會出錯
104             }
105             dfs(u,u,1);
106             for(int i = 0; i < poi.size(); ++i){
107                 _deep = max(_deep,vis[poi[i]]);
108                 vis[poi[i]] = 0;//這里別忘了初始化  不然下組資料的dfs會出錯
109             }
110             max_deep = max(max_deep,_deep);//對每個連通圖跑兩次dfs求樹的直徑，取max
111         }
112     }
113 //    cout << bridge << "   " << max_deep << endl;
114     printf("%d\n",bridge - max_deep +1);
115 }
116 
117 int main(){
118 
119     int u,v;
120     while(~scanf("%d%d",&n,&m) && (n+m)){
121         init();
122         for(int i = 0; i < m; ++i){
123             scanf("%d%d",&u,&v);
124             add(u,v); add(v,u);
125         }
126         solve();
127     }
128 
129 
130     return 0;
131 }

4 4
1 2
1 3
1 4
2 3

11 12
1 2
1 3
3 2
3 4
4 5
4 6
6 7
7 8
7 9
8 9
8 11
9 10

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

8 6
1 2
1 3
1 4
1 5
7 6
6 8

標籤：其他

上一篇：演算法系列 - 01 二分思想

下一篇：797. 差分（一維差分模板題）