图论:Tarjan缩点相关，SCC问题

Posted on Edited on

Preface

学校的$$Tarjan$$模板题都还没过，不知道卡了哪个点；

Content

Problem

对于一个有向无环图$$(DAG)$$,找到其拓扑排序，或者判断有向图是否是$$DAG$$；

在 $$DAG$$ 上，使用$$ DP$$ 求最长（短）路；

对于有向图，利用$$Tarjan$$算法进行缩点，重构$$DAG$$;

孤立的一个点也是一个强连通分量；

对于无向图，利用$$Tarjan$$算法进行缩点，指出割点，割边，点双连通分量，边双连通分量；

单独的一条边带两个端点我们也认为是点双连通分量；

Solution

拓扑排序

对于一个有向图$$G$$，$$G$$是有向无环图的充分必要条件为能进行拓扑排序，拓扑排序的思路是：

  1. 建图，计算所有点的入度；
  2. 所有入度为0的点入队；
  3. 队首出队同时记录队首的拓扑序，队首的所有儿子入读自减，如果有儿子为0则儿子入队，直至队列为空；

记录一个小性质：对于一个$$DAG$$，至少添加几条边才能使它变为强连通图？

我们计算入度为零的点数为$$a$$，出度为零的点数为$$b$$，那么我们至少需要添加的边数为$$max(a,b)$$，如果只有一个点的话，我们不需要添加任何边；

B3644 【模板】拓扑排序 / 家谱树

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=1e5;
class Edge{
    public:
    int to;
    int head;
    int nxt;
    int cnt;
}e[maxn];
vector<int> head;
int indeg[maxn];
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    cnt++;
    indeg[v]++;
}

queue<int> q;
int dot[maxn];
void topusort(int(&indeg)[maxn],int (&dot)[maxn],int n){
    for(int i=1;i<=n;i++){
        if(indeg[i]==0) q.push(i);
    }
    int id=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        dot[++id]=x;
        for(int j=head[x];j!=-1;j=e[j].nxt){
            int y=e[j].to;
            indeg[y]--;
            if(indeg[y]==0) q.push(y);
        }
    }
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n;
    cin>>n;
    head.resize(n+1,-1);
    int cnt=0;
    memset(indeg,0,sizeof(indeg));
    memset(dot,0,sizeof(dot));
    for(int i=1;i<=n;i++){
        int x=0;
        while(cin>>x&&x!=0) add(i,x,cnt);
    }
    topusort(indeg,dot,n);
    for(int i=1;i<=n;i++) cout<<dot[i]<<" ";
    return 0;
}

$$Tarjan$$缩点

关于$$Tarjan$$算法的流程这篇博客图解挺清楚的，稍微总结一下流程：

  1. 深度优先搜索这个图，选取一个根节点（注意整个图可能会有多个连通分支，根节点要遍历所有未访问过的结点）；
  2. 遍历当前根节点的所有儿子，按照时间戳给当前根节点的$$dfn,low$$初始化（$$dfn$$表示在$$dfs$$过程中访问该该节点的序号，也即时间戳，这个值不会更新，$$low$$表示这个点能回访的节点中最小的时间戳，在更新结束后同属于一个强连通分量的点$$low$$值相同），同时根节点入栈，将儿子作为新的根节点继续搜索；
  3. 在搜索图过程中如果搜索到了已经访问过的节点，如果该点还在栈中，那么意味着回访，我们更新当前根节点的$$low$$，搜索开始回溯，同属于一个强连通分量的结点的$$low$$都开始更新为刚刚回访结点的$$low$$值；（注意在栈中这个条件是必须的，如果一个点不在的$$low$$值被不在栈中的点更新了，那么这个点将一直不满足出栈的条件而被留在栈中，典型的反例就是一个点$$P$$指向一个强连通分量的所有点，但强连通分量的点此时均已出栈,$$P$$点的$$low$$会被错误地更新，最终表现为强连通分量的缺少）；
  4. 在所有儿子遍历完成后，检查这个点的$$dfn,low$$是否相等，如果相等那么它作为回访的结点，让它带着同一个强联通分量的点出栈，算法保证了这些点是栈顶部的若干点；

P3387 【模板】缩点

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=1e5+10;
int w[maxn];
vector<int> head;
vector<int> DAGhead;
class Edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn],DAGe[maxn];
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    return ;
}
void DAGadd(int u,int v,int&cnt){
    DAGe[cnt].nxt=DAGhead[u];
    DAGhead[u]=cnt;
    DAGe[cnt].head=u;
    DAGe[cnt].to=v;
    return ;
}

int dfn[maxn];
int low[maxn];
bool instk[maxn];
stack<int> stk;
vector<int> scc[maxn];int sccnum=0;int sccid[maxn];int color[maxn];
int ww[maxn];
int dep=0;

void tarjan(int x){
    dfn[x]=++dep;
    low[x]=dep;
    stk.push(x);
    instk[x]=true;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) low[x]=min(low[x],dfn[y]);
        
    }
    if(dfn[x]==low[x]){
        sccid[++sccnum]=x;
        while(!stk.empty()&&stk.top()!=x){
            int y=stk.top();
            stk.pop();
            instk[y]=false;
            color[y]=sccnum;
            scc[sccnum].push_back(y);
        }
        stk.pop();
        instk[x]=false;
        color[x]=sccnum;
        scc[sccnum].push_back(x);
    }
}

int f[maxn];
void dp(int x){
    if(f[x]) return ;
    f[x]=ww[x];
    int res=0;
    for(int i=DAGhead[x];i!=-1;i=DAGe[i].nxt){
        int y=DAGe[i].to;
        if(!f[y]) dp(y);
        if(res<f[y]) res=f[y];
    }
    f[x]+=res;
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1,-1);
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,i);
    }
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(sccid,0,sizeof(sccid));
    memset(instk,0,sizeof(instk));
    memset(ww,0,sizeof(ww));
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=sccnum;i++) {
        for(int j=0;j<scc[i].size();j++){
            ww[i]+=w[scc[i][j]];
        }
    }
    DAGhead.resize(sccnum+1,-1);
    int cnt=0;
    for(int i=0;i<m;i++){
        int u=e[i].head;
        int v=e[i].to;
        if(color[u]!=color[v]) {
            DAGadd(color[u],color[v],cnt);
            cnt++;
        }
    }
    int ans=0;
    for(int i=1;i<=sccnum;i++){
        if(!f[i]){
            dp(i);
            if(ans<f[i]) ans=f[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

割点

由于割点是相较于无向图的概念所以$$Tarjan$$算法不能直接应用于求出割点，但是我们利用$$Tarjan$$算法的思想魔改一下，根据$$dfn$$序将图中顶点分成若干性质相同的块（$$low$$相同的属于同一个集合）便可以找到割点；

注意这里的$$low$$数组的含义与传统的$$Tarjan$$有略微的不同，更新条件也不一样；

对于无向图$$DFS$$树的相关性质：

  • 对于每个结点的子树之间没有边相连（否则搜索这棵子树的时候一定会顺着这条边把另一棵子树一并搜索，所以另一棵子树将没有机会成为子树，矛盾）

  • 对于非树边的两个端点，其中一个一定是另一个的祖先（非树边不能连接不同子树上的结点，所以非树边的两个端点一定在同一个子树上，自然具有了祖先关系）；

  • 祖先的时间戳一定小于其子孙的时间戳；

  • 对于树边总可以指定一个方向使得父亲指向儿子，相对的，对于无向图中儿子指向父亲的边就是非树边；

对于一个无向连通图，取出其中一棵可能的$$DFS$$树，对于非根结点$$x$$，我们记$$T(x)$$为$%$$$x$$伸展出来的子树（包括$$x$$），那么倘若$$x$$是割点，那么将其删去变得不再连通，对于$$x$$的儿子$$y$$来说，$$y$$通过非树边回访的点$$u$$一定不是$$x$$的祖先，（注意在$$DFS$$无法搜索到未访问的点时，一定是通过非树边回访那些已经访问的点，有些点回访它的父亲，也有的点回访其他祖先，因为不可能在其他子树上），换言之，$$u$$在$$T(x)$$中，因此在所有$$y$$所能回访的节点中，我们维护这些结点最小的$$dfn$$，更新$$low(y)$$；在一个儿子递归结束后，我们用儿子们中的最小$$low$$值更新父亲结点的$$low$$，如果儿子能回访的结点甚至都不能是$$x$$的祖先($$low[y]\ge dfn[x]$$)，那么$$x$$就是割点；

对于根节点则要简单许多，只需要一个特判：如果根节点发出两个及以上真-子树（不包括$$x$$）的话，说明把$$x$$删去就会导致不连通（因为子树之间没有边相连）；

对于一般的图，我们只需要考虑每个连通分量即可；

根据以上描述手搓的一个草图，防止以后看不懂；

P3388 【模板】割点（割顶）

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
#define local
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=200005;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int>head;
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    cnt++;
}
int dep=0;
int dfn[maxn];
int low[maxn];
bool cut[maxn];
stack<int> stk;
void Cut(int now,int fa,int rt){
    dfn[now]=low[now]=++dep;
    int sontree=0;
    for(int i=head[now];i;i=e[i].nxt){
        int sn=e[i].to;
        if(!dfn[sn]){
            sontree++;
            Cut(sn,now,rt);
            low[now]=min(low[now],low[sn]);
            if(low[sn]>=dfn[now]&&now!=rt) cut[now]=1;
        }
        else low[now]=min(low[now],dfn[sn]);
    }
    if(now==rt&&sontree>=2) cut[now]=1;  
    return;
}

int main()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1);
    int cnt=1;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,cnt);
        add(v,u,cnt);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) Cut(i,-1,i);
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(cut[i])ans.push_back(i);
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

割边

一个基本的事实是所有的割点都依附于割边，我们用相同的办法更新相应的$$dfn,low$$数组，但是判定条件略有区别：我们忽略对回边（树边的逆向边）的更新，如果对于边$$xy$$，$$y$$只能能回访到时间戳严格大于$$x$$的点，说明$$xy$$是割边，否则不是；

T103481 【模板】割边

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=6e5+10;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int> head;
void add(int u,int v,int cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].head=u;
}
int rev(int x){
    return x%2?x+1:x-1;
}
int dfn[maxn];
int low[maxn];
bool bdg[maxn];
int dep=0;
void bridge(int x,int eg){
    dfn[x]=low[x]=++dep;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            bridge(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) bdg[i]=bdg[rev(i)]=true;
        }
        else if(eg!=rev(i))
            low[x]=min(low[x],dfn[y]);
    }
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,2*i-1);
        add(v,u,2*i);
    }
    for(int i=1;i<=n;i++)if(!dfn[i]) bridge(i,0);
    int bdgnum=0;
    for(int i=1;i<=2*m;i+=2) {
        if(bdg[i]) bdgnum++;
    }
    cout<<bdgnum<<endl;
    return 0;
}

点双连通分量

称极大的不包含割点的连通块被称为点的双连通分量

点双连通分量是点双连通极大子图；

  • $$BCC$$中无割点
  • 若$$BCC$$间有公共点，那么公共点是原图的割点；
  • 无向连通图中割点至少属于两个$$BCC$$，非割点属于一个$$BCC$$
  • 点双连通不具有传递性；

由上述性质我们知道，割点是每个点双的公共点，在遍历$$DFS$$树时候发现点双意味着割点（或者$$DFS$$的树根）必然最先发现，因此在与有向图求解强连通分量时不同，如果回访到了割点（或者树根），应该立即让子树出栈，包括割点（或者树根），加入新的点双中；

P8435 【模板】点双连通分量

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=4e6+10;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int> head;
void add(int u,int v,int cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
}

int dfn[maxn];
int low[maxn];
int dep=0;
stack<int> stk;
vector<int> bcc[maxn];
bool instk[maxn];
int bccnum=0;
void BCC(int x,int fa){
    dfn[x]=low[x]=++dep;
    stk.push(x);
    int son=0;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            son++;
            BCC(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                bccnum++;
                while(stk.top()!=y) {
                    bcc[bccnum].push_back(stk.top());
                    stk.pop();
                }
                bcc[bccnum].push_back(y);
                stk.pop();
                bcc[bccnum].push_back(x);
            }
        }
        else if(y!=fa) low[x]=min(low[x],dfn[y]);
    }
    if(fa==0&&son==0) bcc[++bccnum].push_back(x);
    return;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,2*i-1);
        add(v,u,2*i);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) BCC(i,0);
    cout<<bccnum<<endl;
    for(int i=1;i<=bccnum;i++){
        cout<<bcc[i].size()<<" ";
        for(int j=0;j<bcc[i].size();j++){
            cout<<bcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

边双连通分量

极大的不含有桥的连通区域被称为边的双连通分量;

观察我们知道把所有的割边删除留下来的连通分支本身构成边连通分量，所以整体与有向图求强连通分量类似；

注意对重边的处理即可；

P8436 【模板】边双连通分量

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=4e6+5;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int> head;
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    cnt++;
}

int dfn[maxn];
int low[maxn];
int dep=0;
int instk[maxn];
stack<int> stk;
vector<int> edcc[maxn];
int edccnum=0;
int rev(int x){
    return x%2?x+1:x-1;
}
void EDCC(int x,int fa,int eg){
    dfn[x]=low[x]=++dep;
    stk.push(x);
    instk[x]=1;
    int revis=0;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            EDCC(y,x,i);
            low[x]=min(low[x],low[y]);
        }
        else if(i!=rev(eg)&&instk[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        edccnum++;
        while(stk.top()!=x){
            edcc[edccnum].push_back(stk.top());
            instk[stk.top()]=0;
            stk.pop();
        }
        edcc[edccnum].push_back(x);
        instk[x]=0;
        stk.pop();
    }
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    int cnt=1;
    head.resize(n+1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,cnt);
        add(v,u,cnt);
    }

    for(int i=1;i<=n;i++) if(!dfn[i]) EDCC(i,0,0);
    cout<<edccnum<<endl;
    for(int i=1;i<=edccnum;i++){
        cout<<edcc[i].size()<<" ";
        for(int j=0;j<edcc[i].size();j++){
            cout<<edcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Example

Gym - 104197K

Remark

重新整理了一遍笔记还是没过学校的逆天模板题，留大坑于此；