POJ 3694 割边+lca

POJ 3694

问题

  • 连通图中给出q个询问,每次询问添加一条边,问添加后割边的数量?

思路

  1. trajan求出割边数量(标记割边中的一点:等价于缩点后存在的点)。
  2. 给出的连接2个点到lca的边上的割边都要取消掉(因为成环了,所以环上不存在割边了)
    • 看题解学的LCA (最近公共祖先)
      1. tarjan时顺带求出搜索树中每个点的深度,lca时先将2个中的深的向上遍历,使得2个点在同一深度。再同时向上遍历找到根节点
      2. 在此过程中维护(取消)割边数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn = 1e5+100;

struct edge { int to,next; } g[maxn*10];
int dfn[maxn],Dfn[maxn],low[maxn],head[maxn],father[maxn];
bool bridge[maxn];
int index1,cnt,res,n,m;

void init() {
    memset(dfn,-1,sizeof dfn);
    memset(head,-1,sizeof head);
    memset(bridge,0,sizeof bridge);
    index1 = cnt = res = 0;
}
void add_edge(int x,int y) {
    g[cnt].to = y;
    g[cnt].next = head[x];
    head[x] = cnt++;
}

void tarjan(int x,int fa) {
    dfn[x] = low[x] = index1++;
    bool f = 1;
    Dfn[x] = Dfn[fa] + 1;
    for (int i=head[x]; i!=-1; i=g[i].next) {
        int to = g[i].to;
        if (to == fa && f) { f=0; continue; } // 搜索树中(来回的2条边)之外的边可以用来更新dfn[]
        if (dfn[to] == -1) {
            father[to] = x;
            tarjan(to,x);
            low[x] = min(low[x],low[to]);
            if (dfn[x] < low[to]) {
                ++res; //记录割边数量
                bridge[to] = 1; //子节点标记一下,标记的点恰好组成了缩点后的图
            }
        } else low[x] = min(low[x],dfn[to]);
    }
}

void lca(int x,int to) {
    if (Dfn[x] < Dfn[to]) swap(x,to);
    while (Dfn[x] > Dfn[to]) {
        if (bridge[x])
            res--,bridge[x] = 0;
        x = father[x];
    }
    while (x != to) {
        if (bridge[x])
            res--,bridge[x] = 0;
        if (bridge[to])
            res--,bridge[to] = 0;
        x = father[x],to=father[to];
    }
}

int main() {
    //freopen("1.in","r",stdin);
    int count1 = 0;
    while (scanf("%d%d",&n,&m) && (n+m)) {
        init();
        for (int i=0; i<m; ++i) {
            int x,y; scanf("%d%d",&x,&y);
            add_edge(x,y);
            add_edge(y,x);
        }
        tarjan(1,0);
        int Q; scanf("%d",&Q);

        printf("Case %d:\n",++count1);

        while (Q--) {
            int x,y;
            scanf("%d%d",&x,&y);
            lca(x,y);
            printf("%d\n",res);
        }
        printf("\n");
    }
    return 0;
}

算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！