@[toc]
简介 拓扑排序是将一张有向图的节点进行排序,使得形成的拓扑序满足一个节点的前驱必然在其前面,一个节点的后继必然在其后面。 拓扑排序是根据各个节点的入度来实现的(即该节点前驱的个数)。首先先将入度为0的节点扔进队列里(即没有前驱的节点),每次弹出一个节点,即已经将他排好序,把它从图中拿出来。因为该节点已经从图中拿出来了,因此要遍历该节点的所有后继,将它的所有后继入度减一。此时如果他的某一个后继入度减一后变成了0,说明该后继在未排序的节点中它已经没有前驱,那就将它丢进队列中,因为队列是先进先出,所以会依此形成有序循环,直到队列为空。 队列为空后,该节点所在的强联通块就已经生成了拓扑序,而未联通的其他分量会不在拓扑序中。而在该联通块中,如果排好的序小于节点数量,说明图中有环。为啥子嘞?因为如果有环的话,环中的节点就会直接的或间接的指向自己,而拓扑排序时的后继检查不检查自己,因此环中节点的入度最后会是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 void topsort (vector<int > edge[101 ],int inDgree[101 ]) { vector<int > shunxu; queue<int >Q; for (int i = 0 ; i < 100 ; i++) if (inDgree[i] == 0 ) Q.push (i); while (!Q.empty ()) { int now = Q.front (); Q.pop (); for (auto e : edge[now]) { if (--inDgree[e] == 0 ) { Q.push (e); shunxu.push_back (e); } } } if (shunxu.size () == 100 ) cout << "无环" ; else cout << "有环" ; }
时间复杂度 设点的数目为V,边为E 正常情况下,每一个节点都要入队一次,而每一条有向边都会贡献一次入度,所以入度减一执行E次。因此时间复杂度为$O(V+E)$。
Q1神经网络 原题传送门->洛谷P1038 根据拓扑序不断更新节点状态知道末尾即可
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 #include <iostream> #include <vector> #include <climits> #include <queue> #include <stack> #include <string> #include <algorithm> #include <set> using namespace std;int inDgree[100 ]{ 0 };struct twice { int p, w; }; struct vertex { int c; vector<twice> next; vertex (int c) :c (c) { } }; vector<vertex> edge; int main () { int n, p; cin >> n >> p; queue<int > Q; for (int i = 0 ; i < n; i++) { int a, b; cin >> a >> b; if (a != 0 ) Q.push (i), edge.push_back ({ a }); else edge.push_back ({ a - b }); } for (int k = 0 ; k < p; k++) { int i, j, w; cin >> i >> j >> w; edge[i - 1 ].next.push_back ({ j - 1 ,w }); inDgree[j - 1 ]++; } while (!Q.empty ()) { int now = Q.front (); Q.pop (); for (auto e : edge[now].next) { inDgree[e.p]--; if (inDgree[e.p] == 0 ) Q.push (e.p); } if (edge[now].c >= 0 ) { for (auto e : edge[now].next) { edge[e.p].c += e.w*edge[now].c; } } } bool flag = false ; for (int i=0 ;i<edge.size ();i++) if (edge[i].c > 0 &&edge[i].next.empty ()) { flag = true ; cout << i + 1 << " " << edge[i].c << endl; } if (!flag) cout << "NULL" ; return 0 ; }
时间复杂度:$O(V+E)$ 完事
Q2排序 原题传送门->洛谷P1347 根据关系建边,加入第一个关系,topsort,第二个,topsort…… 知道出现结果。如果有环,即出现矛盾,如AB,B>C,这就有两层层次,A>B,A>C,就只有一层。换句话说,就是在最长单向路径上的节点数要等于总结点数,即产生一个全序(链状)。
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 #include <iostream> #include <vector> #include <climits> #include <queue> #include <stack> #include <string> #include <algorithm> #include <set> using namespace std;#define _(p) (p-'A' ) struct Edge { vector<int > next; }; struct twice { int a, b; }; vector<Edge> edge; bool vis[26 ]{ false };int inDgree[26 ]{ 0 }, inDgreet[26 ]{ 0 };int top[26 ]{ 0 };int main () { int n, m; cin >> n >> m; edge.resize (26 ); for (int i = 1 ; i <= m; i++) { char a, b; int cnt = 0 ; int points = 0 ; cin >> a; cin.ignore (1 , '<' ); cin >> b; edge[_(a)].next.push_back (_(b)); inDgreet[_(b)]++; vis[_(a)] = vis[_(b)] = true ; for (auto e : vis) if (e == true ) points++; queue<twice> Q; for (int j = 0 ; j < 26 ; j++) inDgree[j] = inDgreet[j]; for (int j = 0 ; j < edge.size (); j++) { if (inDgree[j] == 0 && vis[j]) Q.push ({j,1 }); } int mval = -1 ; while (!Q.empty ()) { twice now = Q.front (); Q.pop (); top[cnt++] = now.a; mval = max (mval, now.b);路径更新 for (auto e : edge[now.a].next) { if (--inDgree[e] == 0 ) Q.push ({ e,now.b + 1 });后继的路径要+1 } } if (cnt != points)如果排序数不等于节点数,说明有环 { cout << "Inconsistency found after " << i << " relations." ; return 0 ; } if (mval == n)最长路径上的节点数达到n个,说明说有待排序点已经生成全序 { cout << "Sorted sequence determined after " << i << " relations: " ; for (int i = 0 ; i < n; i++) cout << char (top[i] + 'A' ); cout << "." ; return 0 ; } } cout << "Sorted sequence cannot be determined." ; return 0 ; }
时间复杂度:$O(m(V+E))$
Q3车站分级 原题传送门->洛谷P1983 这道题需要反着想,在一趟车次中,未经停的站等级一定小于经停的站,所以根据每一趟车次来建图。由此可见这一定是有多个重边的稠密图,所以直接邻接矩阵建图,暴力跑一边拓扑即可,当然这是很辣鸡的方法。貌似还有线段树优化的做法,可是本蒟蒻不会呀 。然后建图的时候每一趟之考虑首发站和重点站,我个emmmmm一开始还每一趟都考虑所有站,emmmmm。
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 #include <iostream> #include <vector> #include <climits> #include <string> #include <queue> #include <functional> #include <set> #include <algorithm> #include <cmath> #include <iomanip> using namespace std;#define il inline #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) struct twice { int point, val; }; int node[1001 ][1001 ];int inDgree[1001 ];bool vis[1001 ];int main () { int n, m; cin >> n >> m; for (int k = 1 ; k <= m; k++) { int t, x, y; cin >> t; cin >> x; t--; vis[x] = true ; while (t--) { cin >> y; vis[y] = true ; } for (int i=x;i<=y;i++) if (vis[i]) { for (int j = x; j <= y; j++) if (!vis[j] && i != j) { if (node[i][j] == 1 ) { node[i][j] = node[j][i] = -1 ; inDgree[i]--; inDgree[j]--; } if (node[j][i] == 0 ) { inDgree[i]++; node[j][i] = 1 ; } } } for (int i = 1 ; i <= n; i++) vis[i] = false ; } queue<twice> Q; for (int i = 1 ; i <= n; i++) if (inDgree[i] == 0 ) Q.push ({ i,1 }); int cnt = 1 ; while (!Q.empty ()) { twice now = Q.front (); Q.pop (); cnt = max (cnt, now.val); for (int i = 1 ; i <= n; i++) { if (node[now.point][i] > 0 ) { if (--inDgree[i] == 0 ) { Q.push ({ i,now.val + 1 }); } } } } cout << cnt; return 0 ; }
时间复杂度: $o(n^{2}m)$