拓扑排序

定义

对一个有向无环图（简称 AOV ）G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v ，若边 (u,v)∈E(G) ，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。AOV 网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列

时间复杂度

对有 N 个顶点和 E 条弧的有向图而言，建立求各顶点的入度的时间复杂度为 O(E)，建零入度顶点栈的时间复杂度为O(N)，在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减 1 的操作在语句中总共执行 E 次，所以总的时间复杂度为 O(n+e)

操作步骤

规则：在一个有向图中，对所有的节点进行排序要求没有一个节点指向它前面的节点

  • 先统计所有节点的入度，对于入度为 0 的节点就可以分离出来，然后把这个节点指向的节点的入度 -1
  • 一直做上述操作，直到所有的节点都被分离出来。
  • 如果最后存在入度不为 0 的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解情况

图示

拓扑序列不唯一：上图还可能是 afcdbe

模板

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
//节点编号1~n
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;//最大节点数量

int n,m;//那个节点m条有向边（关系）
int in[N];//记录每个节点的入度
vector<int> vec[N];//记录每个节点连向的其他节点
queue<int> q;//拓扑用到的队列
vector<int> ans;//记录拓扑结果

void init(){
    for(int i=1;i<=n;i++)
    vec[i].clear();

    while(!q.empty())q.pop();
    ans.clear();
    memset(in,0,sizeof in);
}

void topsort(){
    for(int i=1;i<=n;i++)
    if(in[i]==0)q.push(i);//入度为0的节点入队

    int cnt=0;
    while(!q.empty()){
        int p=q.front();
        q.pop();//拿出一个节点
        cnt++;//弹出该节点并记录弹出数量
        ans.push_back(p);//答案记录节点
        for(int j=0;j<vec[p].size();j++){//弹出节点所连的其他节点入度均-1
            int v=vec[p][j];
            in[v]--;
            if(in[v]==0)q.push(v);//入度为0了可以弹出入队
        }
    }
    
    if(cnt!=n)cout<<"No Answer!"<<endl;//成环
    else{//输出答案
        for(auto x:ans)
        cout<<x<<" ";
        cout<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>m){
        init();
        int x,y;
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            vec[x].push_back(y);
            in[y]++;
        }
        topsort();
    }
    return 0;
}
/*
上图的排序(a-1)
6
8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
output:1 6 3 4 2 5
*/

有些拓扑排序要求字典序最小什么的，那就把队列换成优先队列就好了

应用

主要用来解决一些有向图中依赖解析问题。很抽象的话：目前看到的题就是解决类似一些小学的题，比如做家务有的任务存在先后顺序，有的可以同时完成，让你安排时间使效率最高

模板题：春节到了叔叔想给手下的 n 个工人发奖金，每个人至少要领到888元，其中有m个条件：a 领到的钱至少要比 b 多，叔叔比较抠门想尽可能支出少的钱，让你帮他解决，能满足所有条件输出需要的钱不能输出 -1

思路：没要求的直接给 888 元就可以了，至于 a 领到的钱至少要比 b 多说明 a 有额外的要求，贪心就给 a 在b的奖金基础上额外多发 1 元就好，如此就可以使用拓扑排序解决。反向建边然后另开一个 val[] 记录每个节点额外需要的钱，即每个节点的钱为上一个节点的 val+1

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;//最大节点数量

int n,m;//那个节点m条有向边（关系）
int in[N];//记录每个节点的入度
vector<int> vec[N];//记录每个节点连向的其他节点
queue<int> q;//拓扑用到的队列
int val[N];

void init(){
    for(int i=1;i<=n;i++)
    vec[i].clear();

    while(!q.empty())q.pop();
    memset(in,0,sizeof in);
    memset(val,0,sizeof val);
}

void topsort(){
    for(int i=1;i<=n;i++)
    if(in[i]==0)q.push(i);//入度为0的节点入队

    int cnt=0;
    while(!q.empty()){
        int p=q.front();
        q.pop();//拿出一个节点
        cnt++;//弹出该节点并记录弹出数量
        for(int j=0;j<vec[p].size();j++){//弹出节点所连的其他节点入度均-1
            int v=vec[p][j];
            in[v]--;
            if(in[v]==0)q.push(v),val[v]=val[p]+1;//入度为0了可以弹出入队
        }
    }
    
    if(cnt!=n)cout<<-1<<endl;//成环
    else{//输出答案
        ll sum=0;
        for(int i=1;i<=n;i++)sum+=888+val[i];
        cout<<sum<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>m){
        init();
        int x,y;
        for(int i=1;i<=m;i++){
            cin>>x>>y;//反向建边:x要求比y多反向建边，所以x条件+1
            vec[y].push_back(x);
            in[x]++;
        }
        topsort();
    }
    return 0;
}

经典例题：不同值的升序排序序列是指使用某种形式的小于运算符将元素从最小到最大排序的序列。例如，排序序列 A , B , C , D 意味着 A < B , B < C , C < D 。在这个问题中，我们将给你一组 A < B 的关系，并要求你确定是否已经指定了排序顺序。

思路：参考讲解——此题难在要确定判断输出结果的依据，所以只能边存边排序，其次是对不同状态的判断方法。做法：边读边进行拓扑排序，如果最后拓扑的个数小于 n 说明图中有环返回 0 ，否则看能否条件是否拓扑唯一

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
#include<bits/stdc++.h>
using namespace std;
int n,m,sign;//n个节点m关系，记录能否拓扑唯一
int in[26],out[26];//记录入度和拓扑唯一的输出结果
string s;
vector<int> edge[26];//记录边通向的其他节点
queue<int> q;//拓扑用到的队列

void init(){
	memset(in,0,sizeof in);
	for(int i=0;i<n;i++)
	edge[i].clear();
	sign=0;
}

int topsort(){//返还0,-1或者1
	while(!q.empty())q.pop();
	int cnt=0,flag=1,inc[26];
	for(int i=0;i<n;i++)
	inc[i]=in[i];//拷贝一份入度
	for(int i=0;i<n;i++){
		if(!inc[i])q.push(i);
	} 
	while(!q.empty()){//flag:-1次序不确定；1：次序唯一
		if(q.size()>1)flag=-1;//说明给出的条件不足以判断
		int now=q.front();
		out[cnt++]=now;
		q.pop() ;
		for(int i=0;i<edge[now].size();i++)
		if(--inc[edge[now][i]]==0)
		q.push(edge[now][i]);
	}
	if(cnt!=n)return 0;//队列存在入度不为0的点，成环
	return flag; 
}

signed main()
{
	while(cin>>n>>m){
		getchar();
		if(n==0&&m==0)break;
		init();
		for(int i=1;i<=m;i++){
			cin>>s;
			if(sign)continue;//结论出来了只需要继续存完就行了
			int ch1=s[0]-'A',ch2=s[2]-'A'; 
			edge[ch1].push_back(ch2);
			in[ch2]++;
			int k=topsort();
			if(k==0){//成环 
				printf("Inconsistency found after %d relations.\n",i);
                sign=1;//同时标记为1
			}
			if(k==1){//拓扑唯一：有序
				printf("Sorted sequence determined after %d relations: ",i);
                for(int j=0;j<n;j++)
				printf("%c",out[j]+'A');printf(".\n");
                sign=1;
			}
		}
		if(!sign)printf("Sorted sequence cannot be determined.\n");//最后才确定次序是否唯一
	}
	return 0;
}

强连通分量

 参考博客  参考这篇博客以及队内资料多理解，只是绕但是不难

预备知识

强连通的定义：如果图中节点间可以相互通达则称他们为强连通

强连通图定义：如果有向图 G 的任意节点之间都强连通，称 G 是一个强连通图

强连通分量定义：非强连通图有向图的极大强连通子图，称为强连通分量

注意：单个节点也看做是一个强连通图

例如：在这个有向图中 {1,2,3,4} 四个点可以互相到达，就称这四个点组成的子图为强连通分量（这四个点中任意两两节点强连通），当然 {5}、{6} 也是强连通分量

Tarjan算法求强连通分量

相关知识

关于 DFS 搜索树中的四条边：

  • 树枝边：DFS 时经过的边，即 DFS 搜索树上的边
  • 前向边：与 DFS 方向一致，从某节点指向其某个子孙的边
  • 后向边：与 DFS 方向相反，从某节点指向其某个祖先的边（又称返祖边）
  • 横叉边：从某个节点指向搜索树中的另一子树中的某节点的边

思想介绍

Tarjan算法是借助栈来求强连通分量的算法，它是一种基于 DFS 的算法，每个强连通分量为搜索树中的一棵子树。

在介绍详细原理前，先引入两个关于图中节点非常重要的数组：dfn[] 与 low[]：

  • dfn[] 就是一个时间戳（被搜索到的次序）一旦某个点被DFS到后，这个时间戳就不再改变且每个节点拥有唯一的时间戳，所以所以常根据 dfn 的值来判断是否需要进行进一步的深搜
  • low[] 记录当前节点的子树中能访问到的仍在栈中的最小时间戳，像是确立了某个关系，low 相等的点在同一强连通分量中
  • 初始化时 dfn[i]=low[i]=++cnt

具体做法

  • 首先这个图不一定是连通图（有可能是分为几块），所以枚举每个点 Tarjan ，若 dfn[i]==0 则继续向下DFS（ main() 中)

  • 对于搜到的点先处理当前点的 dfn 和 low 并将该点入栈，然后看与其有边相连的点，判断这些点是否已经被搜索过，若没有则进行搜索。若点已经在栈中，说明形成了环，则更新当前搜索到的点的 low（ Tarjan() 中)

  • 在不断 DFS 的过程中如果当前点没有路可走了（出边遍历完了），那么就进行回溯。回溯时不断更新之前节点的 low ，每个节点都取最小的 low 值。如果回溯完 x 节点时 dfn[x]==low[x] 则 x 可以看作是某一强连通分量子树的根，也说明找到了一个强连通分量，然后对栈进行弹出操作，直到 x 被弹出（ x 和其后面的子节点构成了一个强连通分量）（ Tarjan() 中)

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
void Tarjan(int now){//枚举到当前节点
    //处理当前节点
    dfn[now]=low[now]=++Index;
    stack[++tot]=now;
    vis[now]=1;

    //向下DFS并最后回溯更新low
    for(int i=f[now];i!=-1;i=e[i].next){
        int nex=e[i].v;
        if(!dfn[nex]){//没搜到向下Tarjan
            Tarjan(nex);
            low[now]=min(low[now],low[nex]);//nex点回溯尝试更新当前点low
        }
        else if(vis[nex])low[now]=min(low[now],dfn[nex]);//nex比当前节点提前搜到，直接回溯尝试更新当前节点low
    }

    if(dfn[now]==low[now]){//判断节点是否为某个强连通分量的根节点
        int p;//弹出指针
        do{
            p=stack[tot--];
            vis[p]=0;
            cout<<p<<" ";
        }while(p!=now);//弹出以now为根节点的强连通分量
    }
    cout<<endl;
}

算法演示

就以一个连通图从节点 1 开始 Tarjan 为例，注意这个图示的入栈顺序是由上到下

  • 从节点1开始 DFS ，每搜索到一个节点就处理节点 dfn 和 low（初始 dfn[i]=low[i]=++index ）并将节点放入栈中。当深搜到节点 6 时 dfn[6]==low[6] 所以找到了一个强连通分量，弹出栈内节点 6 和下面的节点 {6}

·

  • 回溯到节点5后还是 dfn[5]==low[5] 所以又找到一个强连通分量，弹出栈内节点 5 和下面的节点 {5}
  • 回溯到节点 3 后还有通向节点4的边所以搜索到节点 4 并把节点 4 放入堆栈。紧接着发现搜索节点4可以到祖辈节点 1（后向边），所以更新 low[4]=1 ，还可以到节点 6 但节点 6 已经出栈（横叉边）所以回溯值节点 3 ，此时节点 3 被更新 low[3]=min(low[3],low[4])=1（ 3 , 4 为树状边）（第一种更新情况）
  • 回溯到节点 1 ，节点 1 还有可以搜索到节点 2 并把节点 2 放入栈中。紧接着搜索节点 2 访问到还在栈中的节点 4 ，所以更新节点 2 为 low[2]=min(low[2],dfn[4])=5（第二种更新情况）。回溯到节点 1 后发现 dfn[1]==low[1] 说明找到以节点 1 为根的强连通分量，弹出节点1及下面的节点 {1,3,4,2}
  • 最终栈内为空结束此次Tarjan算法

模板

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
//节点编号1~n
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;//最大节点数

int n,m;//图的节点数和边数
int tot,Index,top;//链式前向星寄存指针,时间戳指针,栈的栈顶指针
int dfn[maxn],low[maxn];//Tarjan中节点用到的两个重要的属性
int Stack[maxn];//模拟栈
bool vis[maxn];//模拟栈用到的判断节点是否存在栈中

int head[maxn];//链式前向星数组
struct edge{
    int u,v,w;
    int nex;
}e[maxn*maxn];

void init(){
    tot=Index=top=0;
    memset(vis,0,sizeof vis);
    memset(head,-1,sizeof head);
    memset(dfn,0,sizeof dfn);//这里初始化为0为了main中枚举所有的连通图
    //其他的可以不初始化
}

void add(int u,int v,int w){//u,v之间建立权值为w的有向边
    ++tot;
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=head[u];
    head[u]=tot;
}

void Tarjan(int now){//枚举到当前节点
    //处理当前节点并入栈
    dfn[now]=low[now]=++Index;
    Stack[++top]=now;
    vis[now]=1;

    //向下DFS并最后回溯更新low
    for(int i=head[now];i!=-1;i=e[i].nex){
        int nex=e[i].v;
        if(!dfn[nex]){//没搜到向下Tarjan
            Tarjan(nex);
            low[now]=min(low[now],low[nex]);//nex点回溯尝试更新当前点low
        }
        else if(vis[nex])low[now]=min(low[now],dfn[nex]);//nex比当前节点提前搜到，直接回溯尝试更新当前节点low
    }

    if(dfn[now]==low[now]){//判断节点是否为某个强连通分量的根节点
        int p;//弹出指针
        do{
            p=Stack[top--];//取出栈顶元素并缩小栈的大小
            vis[p]=0;
            cout<<p<<" ";
        }while(p!=now);//弹出以now为根节点的强连通分量
        cout<<endl;//输出一组强连通分量并换行
    }
}

signed main()
{
    while(cin>>n>>m){
        init();
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            add(x,y,0);
        }

        for(int i=1;i<=n;i++)//枚举每个节点寻找强连通分量
        if(dfn[i]==0){
            Tarjan(i);
            cout<<endl;//强连通分量之间有一个空行
        }
    }
    return 0;
}
/*
6 8
1 2
1 3
2 4
3 4
3 5
4 1
4 6
5 6
output:
6
5
2 4 3 1
*/

模板题：有 n 个点 m 个有向边组成的有向图，现在要在某些点上设置警察局，在第 i 个点建立警察局的花费是 a[i] ，并且 i 点能保护的点是其所在强连通分量的所有点。现在计划要用最少的花费建立警察局，让你求出最小的花费和可以选择的方案数（在不同的节点建立被认为是不同的方案，对 1e9+7 取模）

思想：用 ans1 记录最小消费，ans2 记录选择种数，最小消费就是各有向图中所有强连通分量的最小节点权值的加和，选择种数根据乘法原理就是各强连通分量中最小权值节点个数的乘积

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
//节点编号1~n
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;//最大节点数
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

int n,m;//图的节点数和边数
int tot,Index,top;//链式前向星寄存指针,时间戳指针,栈的栈顶指针
ll ans1,ans2;//记录最小花费的权值和最小花费下的选择种数
int a[maxn];//记录每个节点的权值
int dfn[maxn],low[maxn];//Tarjan中节点用到的两个重要的属性
int Stack[maxn];//模拟栈
bool vis[maxn];//模拟栈用到的判断节点是否存在栈中

int head[maxn];//链式前向星数组
struct edge{
    int u,v,w;
    int nex;
}e[maxn];

void init(){
    tot=Index=top=0;
    ans1=0,ans2=1;
    memset(vis,0,sizeof vis);
    memset(head,-1,sizeof head);
    memset(dfn,0,sizeof dfn);//这里初始化为0为了main中枚举所有的连通图
    //其他的可以不初始化
}

void add(int u,int v,int w){//u,v之间建立权值为w的有向边
    ++tot;
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=head[u];
    head[u]=tot;
}

void Tarjan(int now){//枚举到当前节点
    //处理当前节点并入栈
    dfn[now]=low[now]=++Index;
    Stack[++top]=now;
    vis[now]=1;

    //向下DFS并最后回溯更新low
    for(int i=head[now];i!=-1;i=e[i].nex){
        int nex=e[i].v;
        if(!dfn[nex]){//没搜到向下Tarjan
            Tarjan(nex);
            low[now]=min(low[now],low[nex]);//nex点回溯尝试更新当前点low
        }
        else if(vis[nex])low[now]=min(low[now],dfn[nex]);//nex比当前节点提前搜到，直接回溯尝试更新当前节点low
    }

    if(dfn[now]==low[now]){//判断节点是否为某个强连通分量的根节点
        int p;//弹出指针
        int minn=inf;//当前强连通分量中最小花费节点的权值
        int sum=0;//与当前强连通分量中最小花费节点权值相同的个数
        do{
            p=Stack[top--];//取出栈顶元素并缩小栈的大小
            vis[p]=0;
            if(a[p]==minn)sum++;//和当前最小花费节点权值相同个数+1
            else if(a[p]<minn)
            sum=1,minn=a[p];//找到更小的花费节点重新计算
        }while(p!=now);//弹出以now为根节点的强连通分量
        ans1+=minn;//整个图的最小花费为各连通图的所有强连通分量最小花费加和
        ans2=(ans2*sum)%mod;//选择种数就是个强连通分量最小花费节点的个数相乘(乘法原理)
    }
}

signed main()
{
    while(cin>>n){
        init();
        for(int i=1;i<=n;i++)cin>>a[i];
        cin>>m;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            add(x,y,0);
        }

        for(int i=1;i<=n;i++)//枚举每个节点寻找强连通分量
        if(dfn[i]==0)Tarjan(i);
        cout<<ans1<<" "<<ans2<<endl;

    }
    return 0;
}