10°

kuangbin专题 专题九 连通图 POJ 3694 Network

题目链接:https://vjudge.net/problem/POJ-3694

题目:给定一个连通图,求桥的个数,每次查询,加入一条边,问加入这条边后还有多少个桥。

思路:tarjan + 并查集 + lca(朴素)

先用tarjan缩点(成环缩点),并存下桥,把每个scc都存下一个源点(源点(boss):以这个点代表这个scc)。

用存下的桥,用并查集重新建图,为了方便之后的操作,并查集建立一颗树,dfn小的在上,dfn大的在下。

lca,用每个点的boss的dfn去跑lca,因为我们建树的方法,总会遇到公共的dfn祖先,把这些点都存下,

最后把这些boss点的dfn都变成祖先的dfn值,这样优化了重复的lca,之后输出答案即可。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 using namespace std;
  6 #define pb push_back
  7 
  8 const int N = (int)5e5+10;
  9 int n,m,tot,tim,top,scc,ans;//点,边,链式前向星,时间戳,栈,连通数
 10 int head[N],dfn[N],low[N],scc_no[N],s[N],fa[N],boss[N];
 11 //链式前向星,dfn,low,联通块编号,栈,父节点,源点
 12 struct node{
 13     int to;
 14     int nxt;
 15 }e[N << 1];
 16 struct _cut{
 17     int x,y;
 18 };
 19 vector<_cut> cut;//
 20 vector<int> poi;//lca
 21 
 22 void init(){
 23     for(int i = 0; i <= n; ++i){
 24         head[i] = -1;
 25         dfn[i] = 0;
 26     }
 27     cut.clear();
 28     scc = tim = tot = 0;
 29 }
 30 
 31 inline void add(int u,int v){
 32     e[tot].to = v;
 33     e[tot].nxt = head[u];
 34     head[u] = tot++;
 35 }
 36 
 37 void tarjan(int now,int pre){
 38     dfn[now] = low[now] = ++tim;
 39     s[top++] = now;
 40 
 41     int to,pre_cnt = 0;
 42     for(int o = head[now]; ~o; o = e[o].nxt){
 43         to = e[o].to;
 44         if(to == pre && pre_cnt == 0) { pre_cnt = 1; continue; }
 45         if(!dfn[to]){
 46             tarjan(to,now);
 47             low[now] = min(low[now],low[to]);
 48             if(dfn[now] < low[to]) cut.pb(_cut{now,to});
 49         }
 50         else if(low[now] > dfn[to]) low[now] = dfn[to];
 51     }
 52 
 53     if(dfn[now] == low[now]){
 54         int p;
 55         ++scc;
 56         fa[now] = now; boss[scc] = now;//记录该scc的源点
 57         do{
 58             p = s[--top];
 59             scc_no[p] = scc;
 60         }while(now != p);
 61     }
 62 }
 63 //得到源点函数
 64 inline int _boss(int x){
 65     return boss[scc_no[x]];
 66 }
 67 //重建图   boss进行并查集
 68 void rebuild(){
 69     ans = cut.size();
 70     int x,y;
 71     for(int i = 0; i < ans; ++i){
 72         x = _boss(cut[i].x);
 73         y = _boss(cut[i].y);
 74         //dfn上小,下大的树
 75         if(dfn[x] > dfn[y]) swap(x,y);
 76         fa[y] = x;
 77     }
 78 }
 79 
 80 void lca(int x,int y){
 81     int fax = _boss(x);
 82     int fay = _boss(y);
 83     if(dfn[fax] == dfn[y]) return;
 84 
 85     poi.pb(fax); poi.pb(fay);
 86     while(dfn[fax] != dfn[fay]){
 87         while(dfn[fax] > dfn[fay]){
 88             --ans;
 89             fax = fa[fax];
 90             poi.pb(fax);
 91         }
 92         while(dfn[fax] < dfn[fay]){
 93             --ans;
 94             fay = fa[fay];
 95             poi.pb(fay);
 96         }
 97     }
 98 
 99     int n = poi.size();//所有boss点dfn改变为祖先的dfn
100     for(int i = 0; i < n; ++i) dfn[poi[i]] = dfn[fax];
101     poi.clear();
102 }
103 
104 int main(){
105 
106     int _case = 0;
107     while(~scanf("%d%d",&n,&m) && (n+m)){
108         init();
109         int u,v;
110         for(int i = 0; i < m; ++i){
111             scanf("%d%d",&u,&v);
112             add(u,v); add(v,u);
113         }
114 
115         tarjan(1,1);
116         rebuild();
117 
118         int q;
119         scanf("%d",&q);
120         printf("Case %d:\n",++_case);
121         while(q--){
122             scanf("%d%d",&u,&v);
123             lca(u,v);
124             printf("%d\n",ans);
125         }
126     }
127 
128 
129 
130     return 0;
131 }

本文转载自博客园,原文链接:https://www.cnblogs.com/SSummerZzz/p/12191524.html

全部评论: 0

    我有话说: