Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

时间：2021-06-28 10:01:45

Tarjan求强连通分量

先来一波定义

强连通：有向图中A点可以到达B点，B点可以到达A点，则称为强连通

强连通分量：有向图的一个子图中，任意两个点可以相互到达，则称当前子图为图的强连通分量

强连通图： 如果在一个有向图中，每两个点都强连通，我们就叫这个图叫强连通图。

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）(一张十分简洁的图）

如图，图中{1,2}就是一个强连通，也是这个图中的一个强连通分量

求强连通分量的算法有三种：

Kosaraju算法，Tarjan算法，Gabow算法(然而我只会用Tarjan求)

这里就稍微介绍一下tarjan求强连通分量

首先要明白几个概念：

时间戳(dfn)：dfn就是在搜索中某一节点被遍历到的次序号，

节点能追溯到的最早的栈中节点的时间戳(low)：low就是某一节点在栈中能追溯到的最早的父亲节点的时间戳。

Tarjan算法就是基于深度优先搜索的算法：把没有标记过时间戳的点放入栈中，然后以它为根进行搜索，搜索完后回溯更新low，保证low一定是最小的，如果发现low[u] == dfn[u]，就把u上面的全部弹出栈内，这些点就构成了强连通分量，而这个u就是一个关键节点：从这个节点能够到达其强连通分量中的其他节点，但是没有其他属于这个强连通分量以外的点能够到达这个点，所以这个点的low[u]值维护完了之后还是和dfn[u]的值一样

这样描述还是太抽象了点，还是走一遍流程吧

cnt为计数器

一张经典的图：

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

搜到1，1入栈，dfn[1] = low[1] = ++cnt，栈内元素：1

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

搜到2，2没被搜过，2入栈，dfn[2] = low[2] = ++cnt，栈内元素：1，2

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

搜到3，3没被搜过，3入栈，dfn[3] = low[3] = ++cnt，站内元素：1，2，3

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

搜到6，6没被搜过，6入栈，dfn[6] = low[6] = ++cnt，站内元素：1，2，3，6

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

6没有出边，此时

发现low[6] == dfn[6]，把6弹出，6为强连通分量

回溯到3，发现low[3] == dfn[3]，把3弹出，3为强连通分量

回溯到2，发现2还可以到5，搜索5

搜到5，5没被搜过，5入栈，dfn[5] = low[5] = ++cnt，栈内元素1，2，5

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

搜到1，发现1被搜过了且在栈内，因为low是节点能追溯到的最早的栈中节点的时间戳，我们要保证low最小，所以我们要更新low[5] = min(low[5],dfn[1]) = 1

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

再搜到6，6被搜过但不再栈内，不管

没有其他边了，回溯，回溯到2，因为low要最小，而后面的low值要<=当前的，所以用后面的更新当前的，更新2的值low[2] = min(low[2],low[5])

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

回溯到1

继续搜，搜到4，4没有被搜过，4入栈，栈内元素：1，2，5，4

再搜到5，发现5在栈内，就更新low[4]，low[4] = min(low[4],dfn[5]) = 5

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

没有其他的边了，然后回溯，回溯到1

发现dfn[1] == low[1]

于是乎我们将所有1上面的元素及1弹栈，得到一个强连通分量1，2，5，4

于是这个图中就有3个强连通分量

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

代码：

//vis[i]表示i是否在栈中
//sum表示是连通块个数
//size[i]表示第i个连通块内的元素个数
//bel[i]表示i属于哪个连通块belong也可以理解为color
stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt;
    vis[u] = ;//标记是否在栈内
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]) {
        ;sum ++;
        while(x != u) {//x枚举栈内元素
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
            size[sum] ++;
        }
    }
}

但因为并不一定所有的点都相连，如

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

所以我们遍历的时候要：

; i <= n; ++ i) if(!dfn[i]) tarjan(i);

例题：

很多题都会用到缩点的思想，所以这里先给出两个练手的

HDU1269迷宫城堡

//求强连通分量的个数是不是等于1
#include <bits/stdc++.h>
using namespace std;
;
int n,m,num,cnt,sum;
int dfn[N],low[N],head[N],bel[N];
bool vis[N];
struct node {
    int v,nx;
}e[N];

template<class T>inline void read(T &x) {
    x = ;;char ch =getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[u]) low[u] = min(dfn[v],low[u]);
    }
    if(dfn[u] == low[u]) {
        ;sum ++;
        while(u != x) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
        }
    }
}

int main() {
    while(scanf("%d%d",&n,&m)) {
         && m == ) break;
        memset(head,-,sizeof(head));
        memset(vis,,sizeof(vis));
        memset(dfn,,sizeof(dfn));
        memset(low,,sizeof(low));
        memset(bel,,sizeof(bel));
        memset(e,,sizeof(e));
        num = sum = cnt = ;
        ,x,y; i <= m; ++ i) read(x),read(y),add(x,y);
        ; i <= n; ++ i) if(!dfn[i]) tarjan(i);
        ) printf("Yes\n");
        else printf("No\n");
    }
    ;
}

HDU 1269

P2863 [USACO06JAN]牛的舞会The Cow Prom

//求联通块内的元素个数是否大于1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1e6;
int n,m,num,cnt,tot,sum,ans;
int a[N],b[N],head[N],size[N],bel[N],dfn[N],low[N];
bool vis[N];
stack<int>s;
struct node {
    int v,nx;
}e[N];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[u]) low[u] = min(dfn[v],low[u]);
    }
    if(dfn[u] == low[u]) {
        int x;sum ++;
        while(u != x) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
            size[sum] ++;
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    read(n),read(m);
    ,x,y; i <= m; i ++) {
        read(x),read(y);
        add(x,y);
    }
    ; i <= n; i ++) if(!dfn[i]) tarjan(i);
    ; i <= sum; i ++) {
        )
        ans ++;
    }
    printf("%d",ans);
    ;
}

P2863

Tarjan缩点

个人觉得分不分开讲一个样，缩点就是在上面的内容之后附加一个操作

其实缩点可以看做是一种解题方法罢

简单说，就是把一个强连通分量里的点做为一个点处理

也就是把bel数组里的元素当成点看就好了

假设我们有一张图长这个样：

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

那我们操作的时候就可以脑补成这样

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）---->Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

emmmm.....一般题目都会说如果相互到达就balabalbala

具体代码呢，就是枚举某个点的连边连向的点，如果在同一分量里，就不予处理，否则就按题目要求处理

; i <= n; ++ i)
    for(int j = head[i]; ~j; j = e[j].nx) {
    int v = e[j].v;
    if(bel[i] != bel[v]) /*.code.*/
}

异常的容易

那就直接看题目吧：

P2002 消息扩散

//求入度为0的点的个数
#include <bits/stdc++.h>
using namespace std;
;
;
int n,m,cnt,sum,ans,num;
int head[N],dfn[N],low[N],bel[N],in[N];
bool vis[N];
struct node {
    int v,nx;
}e[M];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]) {
        int x;sum ++;
        while(x != u) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    read(n),read(m);
    ,x,y; i <= m; ++ i) {
        read(x),read(y);
        if(x == y) continue;
        add(x,y);
    }
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i);
    ; i <= n; ++ i)
        for(int j = head[i]; ~j; j = e[j].nx) {
            int v = e[j].v;
            if(bel[i] != bel[v]) in[bel[v]] ++;
        }
//    for(int i = 1; i <= n; ++ i) cout<<in[bel[i]]<<" ";
    ; i <= sum; ++ i) if(!in[i]) ans ++;
    cout<<ans;
    ;
}

P2002

P2341 [HAOI2006]受欢迎的牛

//找出度为0的点
//代码历史久远，以2002为准
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1e6;
int n,m,tot,sum,ans,cnt,num;
int a[N],b[N],head[N],dfn[N],low[N],size[N],bel[N];
bool vis[N],mark[N];
struct node {
    int v,nx;
}e[N];

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}
stack<int>s;
void tarjan(int u) {

    dfn[u] = low[u] = ++cnt;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]) {
        int x;sum ++;
        while(u != x) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
            size[sum] ++;
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    scanf("%d%d",&n,&m);
    ; i <= m; i ++) {
        scanf("%d%d",&a[i],&b[i]);
        add(a[i],b[i]);
    }
    ; i <= n; i ++) if(!dfn[i]) tarjan(i);
    ; i <= m; i ++) ;
    ; i <= sum; i ++) if(!mark[i]) ans = size[i],tot++;
    ) printf("%d",ans);
    ");
    ;
}

P2341

P2194 HXY烧情侣

/*
tarjan
第一问求所有联通块的块中最小值之和，开一个mn数组在tarjan中记录
根据乘法原理，第二问求所有块中 价值=最小值的个数 的乘积
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6;
;
ll n,m,num,cnt,sum,ans,ans1 = ;
ll mn[N],dfn[N],low[N],bel[N],size[N],a[N],head[N];
bool vis[N];
struct node {
    ll v,nx;
}e[N];

template<class T>inline void read(T &x) {
    x = ;ll f = ;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return;
}

inline void add(ll u,ll v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

stack<ll>s;
void tarjan(ll u) {
    dfn[u] = low[u] = ++ cnt;
    vis[u] = ;
    s.push(u);
    for(ll i = head[u]; ~i; i = e[i].nx) {
        ll v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]) {
        ll x=-;sum ++;
        while(x != u) {
            x = s.top(),s.pop();
            bel[x] = sum,vis[x] = ;
            if(mn[sum] == a[x]) size[sum] ++;
            else if(mn[sum] > a[x]) {
                mn[sum] = a[x];
                size[sum] = ;
            }
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    read(n);
    ; i <= n; ++ i) mn[i] = 0x7fffffff;
    ; i <= n; ++ i) read(a[i]);
    read(m);
    ,x,y; i <= m; ++ i) read(x),read(y),add(x,y);
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i);
    ; i <= sum; ++ i) {
        ans += mn[i];
        ans1 = ans1 * size[i] % mod;
    }
    cout<<ans<<" "<<ans1;
    ;
}

P2194

P2746 [USACO5.3]校园网Network of Schools

//同样历史久远
//1.求缩点后入度为0 的点的个数
//2.求入度为0的点数与出度为0的点的较大值
#include <bits/stdc++.h>
using namespace std;
;
int n,m,num,sum,cnt,j,ans,ans1;
int dfn[N],low[N],size[N],bel[N],x,kk[N][N],head[N];
bool vis[N],mark[N],mark1[N];
struct node {
    int v,nx;
}e[N];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x =  f ? -x : x;
    return;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    s.push(u);
    vis[u] = ;
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]) {
        int x;sum ++;
        while(x != u) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
            size[sum] ++;
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    read(n);
    ; i <= n; ++ i) {
        ; j <= n + ; ++ j) {
            read(x);
            ) break;
            kk[i][j] = x;
            add(i,x);
        }
    }
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i);
    ; i <= n; ++ i) {
        ; kk[i][j] != ; j ++) ,mark1[bel[i]] = ;
    }
    ) {
        printf("%d\n0",sum);
        ;
    }
    ; i <= sum; ++ i) {
        if(!mark[i]) ans ++;
        if(!mark1[i]) ans1 ++;
    }
    printf("%d\n%d",ans,max(ans,ans1));
}

P2194

P2812 校园网络【[USACO]Network of Schools加强版】

//邻接表
#include <bits/stdc++.h>
using namespace std;
;
;
int n,num,sum,cnt,ans1,ans2;
int low[N],dfn[N],head[N],size[N],bel[N];
bool vis[N],mark[N],mark1[N];
struct node {
    int v,nx;
}e[M];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt;;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]) {
        ;sum ++;
        while(x != u) {
            x = s.top(),s.pop();
            bel[x] = sum,vis[x] = ;
            size[sum] ++;
        }
    }
}

int main(int argc, char const *argv[]) {
    memset(head,-,sizeof(head));
    read(n);
    ,x; i <= n; ++ i) {
        ; j <= n + ; ++ j) {
            read(x);
            ) break;
            add(i,x);
        }
    }
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i);
    ; i <= n; ++ i) {
        for(int j = head[i]; ~j; j = e[j].nx) {
            if(bel[i] != bel[e[j].v]) {
                mark[bel[e[i].v]] = ;
                mark1[bel[i]] = ;
            }
        }
    }
    ; i <= sum; ++ i) {
        if(!mark[i]) ans1 ++;
        if(!mark1[i]) ans2 ++;
    }
    printf("%d\n%d\n", ans1,ans2);
    ;
}

P2812

P1407 [国家集训队]稳定婚姻：

/*
主体还是一个tarjan
因为最后还会组成n对情侣的话
找恋人的人和恋人和男方会在一个联通块内
因为男女必须成对出现，所以联通块内的点得个数为偶数，所以联通块内每个人都会配对
经过路径是boy1->girl2->boy2->gril1->boy1
*/
#include <bits/stdc++.h>
using namespace std;
;
;
int n,m,k,num,sum,cnt,tmp;
int head[N],dfn[N],bel[N],low[N],sta[N];
bool vis[N];
string g,b;
map<string,int>mp;
struct node {
    int v,nx;
}e[M];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]) {
        int x;sum ++;
        while(u != x) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    read(n);
    ; i <= n; ++ i) {
        cin>>g>>b;
        mp[g] = i,mp[b] = i + n;
        add(i,i + n);
    }
    read(m);
    ; i <= m; ++ i) {
        cin>>g>>b;
        add(mp[g],mp[b]),add(mp[b],mp[g]);
    }
    ; i <= n * ; ++ i) if(!dfn[i]) tarjan(i);
    ; i <= n; ++ i) {
        if(bel[i] == bel[i + n]) printf("Unsafe\n");
        else printf("Safe\n");
    }
    ;
}

P1407

以下两个可能用到其他小知识

P2169 正则表达式：

//tarjan+最短路
#include <bits/stdc++.h>
using namespace std;
;
;
const int INF = 0x3f3f3f3f;
int n,m,sum,num,num_new,cnt;
int dfn[N],low[N],head[N],head_new[N],bel[N],dis[N];
bool vis[N],vis_new[N];
struct edge {
    int v,nx,w;
}e[N];
struct edge_new {
    int v,nx,w;
}e_new[N];
struct node {
    int id,dis;
    bool operator < (const node &l) const {
        return dis > l.dis;
    }
};

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return;
}

inline void add(int u,int v,int w) {
    e[++num].nx = head[u],e[num].v = v,e[num].w = w,head[u] = num;
}

inline void add_new(int u,int v,int w) {
    e_new[++num_new].nx = head_new[u],e_new[num_new].v = v,e_new[num_new].w = w,head_new[u] = num_new;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt;
    vis[u] = ;
    s.push(u);
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]) {
        int x;sum ++;
        while(u != x) {
            x = s.top(),s.pop();
            vis[x] = ,bel[x] = sum;
        }
    }
}

void dijkstra(int s) {
    priority_queue<node>q;
    memset(dis,INF,sizeof(dis));
    memset(vis_new,,sizeof(vis_new));
    dis[s] = ;
    q.push((node){s,});
    while(!q.empty()) {
        node d = q.top();q.pop();
        int u = d.id;
        if(vis_new[u]) continue;
        vis_new[u] = ;
        for(int i = head_new[u]; ~i; i = e_new[i].nx) {
            int v = e_new[i].v;
            if(dis[v] > dis[u] + e_new[i].w) {
                dis[v] = dis[u] + e_new[i].w;
                q.push((node){v,dis[v]});
            }
        }
    }
}

int main() {
    memset(head,-,sizeof(head));
    memset(head_new,-,sizeof(head_new));
    read(n),read(m);
    ,x,y,z; i <= m; ++ i) read(x),read(y),read(z),add(x,y,z);
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i);
    ; i <= n; ++ i)
        for(int j = head[i]; ~j; j = e[j].nx) {
            int v = e[j].v;
            if(bel[i] != bel[v]) add_new(bel[i],bel[v],e[j].w);
        }
    dijkstra(bel[]);
    printf("%d\n",dis[bel[n]]);
    ;
}

HDU3861：

/*
tarjan缩点求最小路径覆盖集
 */
#include <bits/stdc++.h>
using namespace std;
;
;
int t, n, m, num, num_new, sum, cnt, ans;
int head[N], low[N], dfn[N], link[N], head_new[N], bel[N];
bool vis[N], vis_new[N];
struct node {
    int v, nx;
} e[M], e_new[M];

template<class T>inline void read(T &x) {
    x = ; ; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
     + ch - ', ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}

inline void add_new(int u, int v) {
    e_new[++num_new].nx = head_new[u], e_new[num_new].v = v, head_new[u] = num_new;
}

stack<int>s;
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = ;
    s.push(u);
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int x; sum++;
        while (x != u) {
            x = s.top(), s.pop();
            bel[x] = sum, vis[x] = ;
        }
    }
}

bool dfs(int u) {
    for (int i = head_new[u]; ~i; i = e_new[i].nx) {
        int v = e_new[i].v;
        if (!vis_new[v]) {
            vis_new[v] = ;
             || dfs(link[v])) {
                link[v] = u;
                ;
            }
        }
    }
    ;
}

int main(int argc, char const *argv[]) {
    read(t);
    while (t --) {
        read(n), read(m);
        memset(vis, , sizeof(vis));
        memset(low, , sizeof(low));
        memset(dfn, , sizeof(dfn));
        memset(bel, , sizeof(bel));
        memset(head, -, sizeof(head));
        memset(link, -, sizeof(link));
        memset(head_new, -, sizeof(head_new));
        memset(e, , sizeof(e));
        memset(e_new, , sizeof(e_new));
        ans = num = cnt = num_new = sum = ;
        , x, y; i <= m; ++ i) read(x), read(y), add(x, y);
        ; i <= n; ++i) if (!dfn[i]) tarjan(i);
        ; i <= n; ++i)
            for (int j = head[i]; ~j; j = e[j].nx) {
                int v = e[j].v;
                if (bel[i] != bel[v]) add_new(bel[i], bel[v]);
            }
        ; i <= sum; ++i) {
            memset(vis_new, , sizeof(vis_new));
            if (dfs(i)) ans ++;
        }
        printf("%d\n", sum - ans);
    }
    ;
}

HDU 3861

Tarjan割点&&割边

割点

割点：在无向连通图中，删除一个顶点v及其相连的边后，原图从一个连通分量变成了两个或多个连通分量，则称顶点v为割点，同时也称关节点(Articulation Point)。

一个没有关节点的连通图称为重连通图(biconnected graph)。若在连通图上至少删去k 个顶点才能破坏图的连通性，则称此图的连通度为k。

some小例子

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）                          Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

割点为1的图（删去1和他的边图变成两部分）　　　　　　　连通度为2的图

首先明白几个概念

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）               Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

　　　　　（a）　　　　　　　　　　　　　　　　　　　　（b）

概念：

DFS树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树，如图(b)所示。

树边：如（b）中的实线所示，可理解为在DFS过程中访问未访问节点时所经过的边

回边：如（b）中的虚线所示，可理解为在DFS过程中遇到已访问节点时所经过的边。

观察我们的DFS树（b），发现它有两种情况可能是割点：

1、对于一个根节点u，若有两个及以上的子树，说明u是割点

2、对于非叶子节点u（非根节点），若其子树均没有连向u祖先节点的回边，说明删掉u后，根节点与子树不再相连，则u是割点

对根节点很好处理，只要记录一下它的子树个数就好了，对于非叶节点呢

对！用low数组

我们用low记录节点u或u的子树通过非父子边追溯到最早的祖先节点

low[u] = min(low[u],low[v])（当(u,v)是树边）

low[u] = min(low[u],dfn[v])（当(u,v)是回边且v不等于u的父节点）

对于情况2，(u,v)是树边且当 low[v] ≥ dfn[u] 时，节点u是割点，因为v能回溯到的最早祖先不是u就是v，所以v并不能连到u的祖先上，当删去u时，v和u的祖先不相连，即u是割点

fa的意思就是从哪个点搜过来的，因为是无向图，可能还会搜到之前的点

代码实现：

//cut标记当前点是否是割点
void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++cnt;
    ;//记录子树个数
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            ;//情况2
            if(u == fa) child ++;
        }
        low[u] = min(low[u],dfn[v]);
    }
     && u == fa) cut[u] = ;//情况1
}

例题：

P3388 【模板】割点（割顶）：

#include <bits/stdc++.h>
using namespace std;
;
int n,m,num,cnt,tot;
int dfn[N],low[N],head[N];
bool cut[N];
struct node {
    int v,nx;
}e[N];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++cnt;
    ;
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            ;
            if(u == fa) child ++;
        }
        low[u] = min(low[u],dfn[v]);
    }
     && u == fa) cut[u] = ;
}

int main() {
    memset(head,-,sizeof(head));
    read(n),read(m);
    ,x,y; i <= m; ++ i) read(x),read(y),add(x,y),add(y,x);
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i,i);
    ; i <= n; ++ i) if(cut[i]) tot ++;
    printf("%d\n",tot);
    ; i <= n; ++ i) if(cut[i]) printf("%d ",i);
    ;
}

P3388

P5058 [ZJOI2004]嗅探器

//输出最小的割点编号
#include <bits/stdc++.h>
using namespace std;
;
int n,m,k,num,cnt,x,y;
int dfn[N],low[N],head[N];
bool cut[N],vis[N];
struct node {
    int nx,v;
}e[N];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++cnt;
    ;
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            ;
            if(u == fa) child ++;
        }
        low[u] = min(low[u],dfn[v]);
    }
    ) cut[u] = ;
}

void dfs(int u) {
    vis[u] = ;
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!vis[v]) dfs(v);
    }
}

int main() {
    memset(head,-,sizeof(head));
    read(n);
    while(scanf("%d%d",&x,&y)) {
         && y == ) break;
        add(x,y),add(y,x);
    }
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i,i);
    read(x),read(y);
    ; i <= n; ++ i) {
        if(cut[i]) {
            memset(vis,,sizeof(vis));
            vis[i] = ;
            dfs(x);
            if(!vis[y]) {
                cout<<i;
                ;
            }
        }
    }
    cout<<"No solution";
    ;
}

P5058

割边

割边的话其实也差不多甚至更简单

割边：也叫桥，当且仅当去掉该边之后的子图不连通

割边是用在无向图内的

割边不用记录子树情况，然后再改一句话把low[v] >= dfn[u]改为low[v] > dfn[u]

因为我们割点的时候是把当前节点u的所有的边都删去，而割边只能删一条边，显然，如果u，v之间有两条边的话，如果其中删掉一条边，另一条还和u相连，原图还保持连通

代码：

#include <bits/stdc++.h>
using namespace std;
;
int n,m,num,cnt;
int low[N],dfn[N],head[N];
struct node {
    int v,nx,id;
}e[N];

template<class T>inline void read(T &x) {
    x = ;;char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
     + ch - ',ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u,int v) {
    e[++num].nx = head[u],e[num].v = v,head[u] = num;
}

void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++cnt;
    for(int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]) printf("%d -- %d is a Cutting edge\n",u,v);
        }
        else if(v != fa) low[u] = min(low[u],dfn[v]);
    }
}

int main(int argc, char const *argv[]) {
    memset(head,-,sizeof(head));
    read(n),read(m);
    ,x,y; i <= m; ++ i) {
        read(x),read(y);
        add(x,y),add(y,x);
    }
    ; i <= n; ++ i) if(!dfn[i]) tarjan(i,i);
    ;
}

点双连通分量&&边双连通分量

这东西我是现学现卖的，可能会有些地方不详细

既然我们要求点双连通分量和边双连通分量，那我们就要知道它们是什么

连通：在无向图中，所有的点能相互到达

连通分量：相互连通的子图

点双连通分量：简单说，就是没有割点的子图，也就是删掉一个点后，图仍连通性

边双连通分量：简单说，就是没有割边的子图，也就是删掉一个边后，图仍连通性

如果先看具体定义，出门右转自己搜吧（其实是我懒得放百度链接，万一你们都用wiki呢）

这样说很抽象的话，还是来两张图好了

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）　　　　　　　　Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

　　　　　　（1）　　　　　　　　　　　　　　　　　　　　　　（2）　　　　　　　

如图（1）所示：1是割点，{1,2,4,3} 是一个点双连通分量，{1,5,7,6} 也是一个点双连通分量，不难发现，割点可能存在于多个点双连通分量里，而其他点只可能存在于一个点双连通分量里，同时，{1,2,3,4,5,6,7,8} 也是一个边双连通 分量；

如图（2）所示，1-4 是割边，在这个图内 {1,2,3} 和 {4,5,6} 分别组成了连个边双连通分量

求点双连通分量：

对于点双连通分量，在求割点的时候就可以顺便求出，但这是我们要建立一个栈，然后在搜索图的时候，让边入栈，如果遇到 low[v] ≥ dfn[u] 即u是割点的时候，将 u - v 这条边之上的边全部弹出，这些边以及相邻的点就组成了一个点双连通分量，割点可能会属于多个双连通分量，其余的点只会属于一个双连通分量；

文字还是太无力，简单走一下流程：

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

一张简单图：

我们从1开始搜索，dfn[1] = 1,low[1] = 1

搜到2，2没被搜过（时间戳dfn），dfn[2] = 2,low[2] = 2，边 1-2 入栈，栈内元素：{1-2}

搜到3，3没被搜过，dfn[3] = 3,low[3] = 3，边2-3入栈，栈内元素：{1-2，2-3}

搜到4，4没被搜过，dfn[4] = 4,low[4] = 4，边3-4入栈，栈内元素：{1-2，2-3，3-4}

搜4，搜到了2，2被搜过，且4不是2搜过来的，low[4] = min(low[4],dnf[2]) = 2，2-4入栈，栈内元素：{1-2，2-3，3-4，4-2}

回到3，low[3] = min(low[3],low[4]) = 2

回到2，low[3] == low[2] 所以 2 是割点，弹栈，将边 2-3 以上的边全部弹出，将他们边连的顶点存入一个数组内，记为一个双连通分量

最后回到1，dfn[1] == low[1]，弹栈，所以{1,2}也是一个点双连通分量

这样，我们就找到了点双联通分量 {1,2}，{2,3,4}；

这里同样还是用fa记录从那个点搜到了当前点

code：

int dfn[N], low[N], head[N], bel_bcc[N], mn[N];
bool cut[N];

struct edge {//从u到v的边
    int u, v;
};
struct node {//建图用
    int v, nx;
} e[N];

stack<edge>s;//栈内存的是边，
vector<int>bcc[N];

inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cnt;
    ;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!dfn[v]) {
            s.push((edge) {u, v});
            child ++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {//是割点
                cut[u] = ;
                bcc_sum ++;//点双的个数++
                // bcc[bcc_sum].clear();
                ) {
                    edge d = s.top(); s.pop();
                    if (bel_bcc[d.u] != bcc_sum) bcc[bcc_sum].push_back(d.u),bel_bcc[d.u] = bcc_sum;//标记某点在这个电双块内
                    if (bel_bcc[d.v] != bcc_sum) bcc[bcc_sum].push_back(d.v),bel_bcc[d.v] = bcc_sum;
                    if (d.u == u && d.v == v) break;//弹栈一直到u-v
                }
            }
        } else if (dfn[v] < dfn[u] && v != fa) {//回边
            s.push((edge) {u, v});
            low[u] = min(low[u], dfn[v]);
        }
    }
     && child == ) cut[u] = ;//把根节点看做普通节点了，所以下面最后的特殊判断必需。
}

例题：#1190 : 连通性·四

求边双连通分量：

边双联通分量可能简单些，

简单说，就是找到桥（割边）后，把桥删掉，剩下很多连通块，每一个连通块就是一个边双连通分量

因为把图中的桥删掉后，剩下的边都不是桥，既然不是桥，就不能把连通块分成多部分，所以剩下的连通块满足边双连通的定义，所以剩余的连通块都是边双联通

桥不属于任何一个边双连通分量，其余的边和每个顶点，都属于且只属于一个边连通分量

所以我们要做的就只有求桥，删边，染色DFS

code：

;
];
void tarjan(int x, int in_edge) {
    dfn[x] = low[x] = ++cnt;
    for (int i = head[x]; ~i; i = e[i].nx) {
        int y = e[i].y;
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            ] = ;
        }
        ))
            low[x] = min(low[x], dfn[y]);
    }
}
;
void dfs(int x, int color) {
    block[x] = color;
    ; i = e[i].nx) {
        int y = e[i].y;
        if (cut[i]) continue;
        if (!block[y]) dfs(y, color);
    }
}
void get_edccs() {
    ; i <= n; i++)
        if (!block[i])
            dfs(i, ++dcc);
}

例题：

poj3352

Tarjan应用之——LCA

既然说到了Tarjan，那就不得不说一下它的应用，求LCA

Tarjan求LCA是一个O(n+m)的离线做法，查询是O(1)的

Tarjan求LCA其实就是深搜+并查集

先把算法流程摆上

1、任意选一个点为根节点

2、把当前节点u的father设为u，看与u相邻的点v，若v没被搜过，深搜v，深搜完后，把father[v]设成u

3、搜完一个点u后，开始判断与它相关的询问，如果另一个点被搜过，LCA就是另一个点的祖先

我相信看完了我的描述之后，你们还是不知道什么意思

那我们还是手模一下它的流程：

假设我们有这么一张图：

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

我们要查询2-4，5-6，4-7，6-8的LCA

从1开始搜索，fa[1] = 1,vis[1] = 1

搜到2，fa[2] = 2,vis[2] = 1

搜到3，fa[3] = 3,vis[3] = 1;

搜到4，fa[4] = 4,vis[4] = 1;

搜到6，fa[6] = 6,vis[6] = 1;

到此为止，我们就得到了这样的图　

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

发现6没有别的连边了，开始回溯

我们看到有一个关于6的询问6-8，发现vis[8] = 0,不管

回溯到4，fa[6]=4，发现和4有关的询问2-4，于是lca(2,4) = find(2) = 2 ，记录一下//find是找祖宗函数，并查集里常用

回溯到3，发现还有一条边，继续搜

搜到5，fa[5] = 5,vis[5] = 1

5没有别的连边，找和5相关的询问5-6，lca(5,6) = find(6) = 3，记录一下

回溯到3，fa[5] = 3

回溯到2，fa[3] = 2

回溯到1，fa[2] = 1

这样左边的就搜完了

得到

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

回溯到1

继续搜，搜到7，fa[7] = 7,vis[7] = 1

搜到8，fa[8] = 8,vis[8] = 1;

8没有其他的连边，发现有一个和8相关的询问6-8，lca(6,8) = find(6) = 1

回溯到7，fa[8] = 7,发现一个和7相关的询问4-7，lca(4,7) = find(4) = 1

回溯到1，fa[7] = 1

Tarjan总结（缩点+割点(边)+双联通+LCA+相关模板）

到此为止，我们已经把整棵树dfs了一遍，也处理处了所有的询问的结果

最后直接输出就好了

看代码：

P3379 【模板】最近公共祖先（LCA）

//e是记录原图，_e是记录询问
//lca记录的是第i组询问的结果
#include <bits/stdc++.h>
using namespace std;
;
int n, m, k, num, _num;
int fa[N], head[N], _head[N];
bool vis[N];
struct node {
    int v, nx, lca;
} e[N], _e[N];

template<class T>inline void read(T &x) {
    x = ; ; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
     + ch - ', ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}

inline void _add(int u, int v) {
    _e[++_num].nx = _head[u], _e[_num].v = v, _head[u] = _num;
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void tarjan(int u) {
    fa[u] = u, vis[u] = ;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!vis[v]) {
            tarjan(v);
            fa[v] = u;
        }
    }
    for (int i = _head[u]; ~i; i = _e[i].nx) {
        int v = _e[i].v;
        if (vis[v]) {
            _e[i].lca = find(v);
            ) _e[i + ].lca = _e[i].lca;//因为是加的双向边，奇数边是从父到子加的，偶数边是从子到父加的，两者相同
            ].lca = _e[i].lca;
        }
    }
}

int main(int argc, char const *argv[]) {
    memset(head, -, sizeof(head));
    memset(_head, -, sizeof(_head));
    read(n), read(m), read(k);
    , x, y; i < n; ++ i) read(x), read(y), add(x, y), add(y, x);
    , x, y; i <= m; ++ i) read(x), read(y), _add(x, y), _add(y, x);
    tarjan(k);
    ; i <= m; ++ i) printf(].lca);
    ;
}

例题：

P2912 [USACO08OCT]牧场散步Pasture Walking

//dis[i]表示到i的距离
//这一类题，dis直接在Tarjan中计算就好了
#include <bits/stdc++.h>
using namespace std;
;
int n, m, num, _num;
int head[N], _head[N], fa[N], dis[N];
bool vis[N];
struct node {
    int v, nx, w, lca, ans;
} e[N], _e[N];

template<class T>inline void read(T &x) {
    x = ; ; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
     + ch - ', ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u, int v, int w) {
    e[++num].nx = head[u], e[num].v = v, e[num].w = w, head[u] = num;
}

inline void _add(int u, int v) {
    _e[++_num].nx = _head[u], _e[_num].v = v, _head[u] = _num;
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void tarjan(int u) {
    fa[u] = u, vis[u] = ;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!vis[v]) {
            dis[v] = dis[u] + e[i].w;
            tarjan(v);
            fa[v] = u;
        }
    }
    for (int i = _head[u]; ~i; i = _e[i].nx) {
        int v = _e[i].v;
        if (vis[v]) {
            _e[i].lca = find(v);
            _e[i].ans = dis[u] + dis[v] - dis[_e[i].lca] * ;
            ) _e[i + ].lca = _e[i].lca, _e[i + ].ans = _e[i].ans;
            ].lca = _e[i].lca, _e[i - ].ans = _e[i].ans;
        }
    }
}

int main(int argc, char const *argv[]) {
    memset(head, -, sizeof(head));
    memset(_head, -, sizeof(_head));
    read(n), read(m);
    , x, y, z; i < n; ++ i) read(x), read(y), read(z), add(x, y, z), add(y, x, z);
    , x, y; i <= m; ++ i) read(x), read(y), _add(x, y), _add(y, x);
    tarjan();
    ; i <= m; ++ i) printf(].ans);
    ;
}

P2912

一般的LCA都可以做的吧。。（我做题少，而且都是用倍增做的，如有什么不可以题的话还请告知我一下）

相关文章