POJ 3694

题目大意：给出一副联通的无向图，求加上一条边后还有多少条桥，多次加边。

解：其实就是tarjan求桥加lca，这里可以朴素记录深度，向上回溯，取消桥的标记即可。我挺二的，首先把最少边使得不存在双连通分量和加边取消双连通分量搞反了，然后去看了lca和rmq，lca不是很懂tarjan的做法，有空去看下。然后就是做题的时候记录了哪些边是桥，wa，其实只要记录点即可，如果一个点是桥标记，则说明他到他父亲这条边是桥，ac。然后_gxx的做法很神奇，首先遍历出一棵树，然后把剩下的原始边加上去，lca，覆盖桥标记（一开始的全是桥），然后新加的边也是这样处理即可。还有就是桥标记的判断是dfn[x]<low[dest]而非low[x]<low[dest]，这个是个wa点。

View Code

  1 //poj 3694
  2 const
  3          maxn=111111;
  4          maxm=211111;
  5 type
  6         data=record
  7           dest, next: longint;
  8         end;
  9 var
 10         edge: array[1..maxm*2]of data;
 11         pre, vect, dfn, low, dep: array[1..maxn]of longint;
 12         brid, visit: array[1..maxn]of boolean;
 13         test, n, m, tot, ans, time, q: longint;
 14 procedure add(x, y: longint);
 15 begin
 16   inc(tot);
 17   with edge[tot] do begin
 18     dest := y;
 19     next := vect[x];
 20     vect[x] := tot;
 21   end;
 22   inc(tot);
 23   with edge[tot] do begin
 24     dest := x;
 25     next := vect[y];
 26     vect[y] := tot;
 27   end;
 28 end;
 29 
 30 procedure init;
 31 var
 32         i, x, y: longint;
 33 begin
 34   tot := 0; ans := 0;
 35   fillchar(vect, sizeof(vect), 0);
 36   for i := 1 to m do begin
 37     readln(x, y);
 38     add(x, y);
 39   end;
 40 end;
 41 
 42 procedure tarjan(x: longint);
 43 var
 44         i: longint;
 45         flag: boolean;
 46 begin
 47   visit[x] := true;
 48   inc(time);
 49   dfn[x] := time; low[x] := time;
 50   i := vect[x]; flag := true;
 51   while i<>0 do
 52     with edge[i] do begin
 53       if (pre[x]=dest)and(flag) then begin
 54         i := next; flag := false;
 55         continue;
 56       end;
 57       if dfn[dest]=0 then begin
 58         pre[dest] := x;
 59         dep[dest] := dep[x] + 1;
 60         tarjan(dest);
 61         {if low[x]>=low[dest] then low[x] := low[dest]
 62           else begin
 63             inc(ans);
 64             brid[dest] := true;
 65           end;  }
 66         if low[dest]>dfn[x] then begin
 67           inc(ans);
 68           brid[dest] := true;
 69         end;
 70         if low[dest]<low[x] then low[x] := low[dest];
 71       end
 72         else begin
 73           if visit[dest] then
 74             if dfn[dest]<low[x] then low[x] := dfn[dest];
 75         end;
 76       i := next;
 77     end;
 78   visit[x] := false;
 79 end;
 80 
 81 procedure print;
 82 begin
 83   writeln(ans);
 84 end;
 85 
 86 procedure lca(x, y: longint);
 87 var
 88         i: longint;
 89 begin
 90   if dep[x]<dep[y] then begin
 91     i := x; x := y; y := i;
 92   end;
 93   while dep[x]>dep[y] do begin
 94     if brid[x] then begin
 95       dec(ans);
 96       brid[x] := false;
 97     end;
 98     x := pre[x];
 99   end;
100   while x<>y do begin
101     if brid[x] then begin
102       dec(ans);
103       brid[x] := false;
104     end;
105     if brid[y] then begin
106       dec(ans);
107       brid[y] := false;
108     end;
109     x := pre[x]; y := pre[y];
110   end;
111 end;
112 
113 procedure main;
114 var
115         i, x, y: longint;
116 begin
117   fillchar(visit, sizeof(visit), 0);
118   fillchar(pre, sizeof(pre), 0);
119   fillchar(dfn, sizeof(dfn), 0);
120   fillchar(dep, sizeof(dep), 0);
121   fillchar(brid, sizeof(brid), 0);
122   tarjan(1);
123   readln(q);
124   for i := 1 to q do begin
125     readln(x, y);
126     lca(x, y);
127     print;
128   end;
129 end;
130 
131 begin
132   assign(input,'1.txt'); reset(input);
133   test := 0;
134   repeat
135     inc(test);
136     readln(n, m);
137     if n+m=0 then break;
138     writeln('Case ', test, ':');
139     init;
140     main;
141     writeln;
142   until false;
143 end.