割点和桥模板

Posted on | In ,

寻找连通图的割点和桥用的也是tarjan算法，我们计算每个点不经过父亲能到达点的最小dfs序，如果是大于等于父亲的，则说明去掉父节点，该点即无法同上面连通，所以父节点是割点。桥类似，我们对于每个点标记它到父亲的那条边是否是桥。

cf1277E：

给出一个图求对于两点ab，有多少对xy使得从x到y的每一条路径都必经ab。

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
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+1;
const int maxm=5e5+1;
#define ll long long
#define fo(i,n) for(int i=0;i<=n;i++)
struct edge{
    int to,next;
}es[maxm*2];
int head[maxn];
int cnt;
void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
int dfn[maxn],low[maxn];    //low是表示不通过父节点能回到的最小节点
int ind;
int cut[maxn];

void tarjan(int x,int fa){
    dfn[x]=low[x]=++ind;
    int child=0;
    for(int i=head[x];i;i=es[i].next){
        int v=es[i].to;
        if(!dfn[v]){
            child++;
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(!cut[x]){
                if(fa!=x&&low[v]>=dfn[x]){  //子节点不能到达比父亲小的节点,
                    //相等表示另有一条路能回到父节点，如果是桥，要去掉等号
                    cut[x]=1;
                }
            }
        }else if(v!=fa){    //遇到已经到达过的且不是父亲，说明可以绕道回去
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(fa==x&&child>1&&!cut[x]){    //根节点判断方法不一样
        cut[x]=1;
    }
}
int flag[maxn];
bool vis[maxn];
void dfs(int x,int f,int stop){
    flag[x]+=f;vis[x]=1;
    for(int i=head[x],v;i;i=es[i].next){
        v=es[i].to;
        if(!vis[v]&&v!=stop)
            dfs(v,f,stop);
    }
}

int t,n,m;
int main(){
    cin>>t;
    while(t--){
        int a,b;
        cin>>n>>m>>a>>b;
        for(int i=1;i<=n;i++){
            dfn[i]=0;
            low[i]=0;
            cut[i]=0;
            head[i]=0;
        }
        for(int i=0,x,y;i<m;i++){
            cin>>x>>y;
            add(x,y);
            add(y,x);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                cnt=0;
                tarjan(i,i);
            }
        }
        ll res=0;
        if(cut[a]&&cut[b]){
            fo(i,n) flag[i]=0;
            fo(i,n) vis[i]=0;
            dfs(a,1,b);
            fo(i,n) vis[i]=0;
            dfs(b,2,a);
            int anum=0,bnum=0;
            for(int i=1;i<=n;i++){
                if(flag[i]==1)
                    anum++;
                if(flag[i]==2)
                    bnum++;
            }
            res=((ll)anum-1)*(bnum-1);
        }
        cout<<res<<endl;
    }
    return 0;
}

桥的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  father[u] = fa;
  low[u] = dfn[u] = ++dfs_clock;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else if (dfn[v] < dfn[u] && v != fa) {
      low[u] = min(low[u], dfn[v]);
    }
  }
}