电子商务网站建设需要怎么叫人做网站

电子商务网站建设需要,怎么叫人做网站,自己做的网站如何上传,建设工程质量协会网站最近学了些新算法#xff0c;过来做下笔记#xff0c;以免以后忘了。前置知识Tarjan 算法的时间复杂度为 #xfffd;(#xfffd;#xfffd;)O(nm)。在除了求最近公共祖先的 Tarjan 算法里#xff0c;都会用到两个数组和一个概念#xff0c;在这里写清楚一点#xff…最近学了些新算法过来做下笔记以免以后忘了。前置知识Tarjan 算法的时间复杂度为()O(nm)。在除了求最近公共祖先的 Tarjan 算法里都会用到两个数组和一个概念在这里写清楚一点以免后面讲得云里雾里。对图深搜时每一个节点只访问一次被访问过的节点与边构成搜索树。时间戳dfn​dfnx​​表示节点​x​ 第一次被访问的顺序。追溯值low​lowx​​从节点​x​ 出发最早能访问到的最早时间戳。当然这两个数组的含义在不同的 Tarjan 算法中都会有所变化到时我会讲清楚的。最近公共祖先LCA题目最近公共祖先。在最近公共祖先里Tarjan 算法是一个离线算法。离线算法是指在开始处理数据前所有输入数据已知且不可更改的算法例如离散化就是一个经典的代表。‌众所周知朴素 LCA 的单次查询在最坏情况下的时间复杂度为()O(n)n 为总节点数因此就有了改进算法将单次查询的时间提高至(log⁡)O(logn)。但是能否使我们每一次对树的遍历更有价值一些呢可不可以一次遍历获得不止一个答案甚至是所有答案呢Tarjan 算法表示这是可以做到的。知周所众在以​u​ 为根的子树下任意两个不属于同一颗以​u​ 的儿子为根的子树的节点听起来有点晕它们的 LCA 就是​u​。简单来说设son,​sonu,i​​ 表示节点​u​ 的第​i​ 个儿子​x​ 属于son,​sonu,i​​ 的子树​y​ 属于son,​sonu,j​​ 的子树。只要≠​ij​那么​x​ 与​y​ 的 LCA 就是​u​。利用这一性质我们可以想到一个做法使用 DFS 遍历每一个节点x将x 的子树存入以x 的父亲为首的集合里面。接着枚举与x 有关的问题即在 DFS 开始前离线出来的问题若问题为“求出,x,y 的 LCA”且y 已经被访问过了那么这个问题的答案即为y 的首领。维护首领需要用到并查集但是这个并查集其实是有点问题他只能让节点x 的集合变成x 父亲节点的集合即 fa[x] father而其它的操作都正常。这样做的目的是为了维护每个节点的当前最大祖先以达到回答问题的效果。不过为什么在问题为“求出,​x,y​ 的 LCA”中答案是 find(v) 而不是 find(x) 呢因为我们已经要求了​y​ 是已经被访问过的节点了也就是说​y​ 所在的集合首领已经让​y​ 成为这个集合中的一个了而​x​ 由于还在访问所以是无法看到自己的最大祖先的。因此我们这里就选择使用 find(y) 来当答案啦cpp#include bits/stdc.husing namespace std;const int N 500010, M 2 * N;int n, m, s, a, b;vectorint linker[N];struct node { int v, w; };vectornode query[N];int fa[N], vis[N], ans[M];int find(int x) {if (x fa[x]) return x;return fa[x] find(fa[x]);}void tarjan(int x) {vis[x] 1; // 做访问标记for (auto to : linker[x])if (!vis[to]) { // 不能是自己的父亲tarjan(to); // 接着向下访问fa[to] x; // 并查集将节点指向节点父亲// 注意上述两行代码不能反过来不然它们的 fa[to] 就都是 root 了}for (auto i : query[x]) {int v i.v, w i.w;// 一定要访问过不然无意义if (vis[v]) ans[w] find(v);// find(v) 才是真答案因为 find(v) 已经将 v 的集合首领变为 find(v) 了而 x 还没有// 可以这么想一想如果 v 和 x 不属于同一颗 LCA 的儿子的子树那么既然 v 已经访问完毕答案肯定是 v 的集合首领}}int main() {cin n m s;for (int i 1; i n; i) {scanf(%d%d, a, b);linker[a].push_back(b);linker[b].push_back(a);}// 离线for (int i 1; i m; i) {scanf(%d%d, a, b);query[a].push_back({b, i});query[b].push_back({a, i});}for (int i 1; i N; i) fa[i] i; // 并查集初始化tarjan(s);for (int i 1; i m; i)printf(%d\n, ans[i]);return 0;}强连通分量SCC题目The Cow Prom S。强连通分量如果一张有向图它的任意两个节点都可以互相到达我们称之为强连通图。如果是一张图的极大的强连通子图我们称之为强连通分量。如图1,2,3,41,2,3,4 组成了一个强连通分量但1,2,3,4,51,2,3,4,5 组成的就不是好了现在要用到前面说到的dfndfn 数组和lowlow 数组了忘记的回去看。使用 DFS 遍历每一个节点当枚举到x 时初始化dfndfnx​与lowlowx​并且将其压入栈内这个栈是用来存储强连通分量的节点的cppdfn[x] low[x] tim; // 这个 tim 是全局变量stk[top] x, vis[x] 1; // 将 x 放入栈中并打上标记接着枚举x 的邻点v分三种情况若v 尚未访问那么对v 深搜并用lowlowv​更新lowlowx​。因为x 是v 的父节点v 能到达的地方x 也能到达。若v 已访问且在栈中说明v 是左子树节点或者祖先节点。使用dfndfnv​更新lowlowx​。此处使用lowlowv​更新lowlowx​可能会被其它强连通分量给污染。若v 已访问且不在栈中说明v 已经被其所在的强连通分量处理了不需要管它。cppfor (int v : linker[x]) {if (!dfn[v]) {tarjan(v);low[x] min(low[x], low[v]);} else if (vis[v])low[x] min(low[x], dfn[v]);}之后处理强连通分量。若当前枚举到的x 满足dfnlowdfnx​lowx​也就表示x 能到达的最小时间戳的节点就是自己也就代表着x 是一个强连通分量上的一个点那么在栈中在它后面放入的点且现在还在栈中的点与它就可以组成一个强连通分量。所以接下来只要把栈中比x 后加入栈的节点取出来就可以了。cppif (dfn[x] low[x]) {cnt;while (1) {int y stk[top--]; // 取出节点vis[y] 0; // 取消进栈标记scc[y] cnt; // 记录强连通分量中的节点属于哪一个分量siz[cnt]; // 记录强连通分量大小if (x y) break; // 枚举到 x 出栈就可以了}}为了完成这道题这里继续给出主函数代码比较简单如果前面的看懂了主函数肯定不成问题cppint main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin n m;for (int i 1; i m; i)cin a b, add(a, b);for (int i 1; i n; i) // 整个图可能不连通要一一枚举if (!dfn[i]) tarjan(i);for (int i 1; i cnt; i)if (siz[i] 1) ans;cout ans endl;return 0;}割点题目割点。割点在一张无向图中如果去掉一个点可以使图的连通块增加则这个点被称之为割点。如图4​4​ 就是一个割点好吧这个算法也是要用到dfndfn 和lowlow 的而且我可以提前告诉你割点算法与强连通分量的代码长得很像需要好好区分。还是使用 DFS 枚举​x​分两种情况若​x​ 不为根节点当搜索树上存在一个​x​ 的儿子​y​满足low≥dfn​lowy​≥dfnx​​则​x​ 为割点。若​x​ 为根节点当搜索上存在两个​x​ 的儿子满足上述条件时​x​ 为割点。那么low≥dfnlowy​≥dfnx​是什么意思呢这个不等式其实代表着y 最远能到达的最小的时间戳也不会超过x 的时间戳也就表示着x 的父亲节点y 是碰不着的那么此时如果断开必定会增加至少一个连通块。那么为什么根节点需要拥有两个这样的儿子呢举个例子你就知道了。如图11 作为根节点有着22 这样满足条件的儿子但是将其去掉后图的连通块仍然是11好了在知道以上判断条件后代码也不难写出了.但是还是要注意一点数据是有重边的而重边就可以往回走了。但是我们这个判断就直接把这个机会给“杀死”了。因此我们不能根据顶点来判断而是要根据边来判断条件是不能走上一次走过的边。我们为了判边就需要给 vector 多绑上一个 int 保存边的编号以判断。cpp// Tarjan算法 O(n m)#includebits/stdc.husing namespace std;const int N 20010;int n, m, a, b, ans;vectorint linker[N], ne[N];int dfn[N], low[N], tim, top;int iscut[N];void add(int a, int b) {linker[a].push_back(b);}void tarjan(int x, int isroot) {dfn[x] low[x] tim;int child 0;for (int v : linker[x]) {if (!dfn[v]) {tarjan(v, 0);low[x] min(low[x], low[v]);if (low[v] dfn[x]) child;} else low[x] min(low[x], dfn[v]);}if (!isroot child 1 || isroot child 2) iscut[x] 1;}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin n m;for (int i 1, a, b; i m; i) {cin a b;add(a, b), add(b, a);}for (int i 1; i n; i) // 可能不连通if (!dfn[i]) tarjan(i, 1);for (int i 1; i n; i)ans iscut[i];cout ans endl;for (int i 1; i n; i)if (iscut[i]) cout i ;return 0;}割边题目炸铁路。注本题使用暴力解法也可以通过 因此你可以不用学这个算法。割边给定一张无向图若存在一条边将这条边去掉后整个图的连通块数量增加则这条边为割边。如图边[4,5][4,5] 就是一条割边好吧我就告诉你吧其实 Tarjan 算法长得都挺像的除了那个 LCA 以外还是使用 DFS 算法设当前枚举到​x​若​x​ 存在一个子节点​y​满足lowdfn​lowy​dfnx​​则[,]​[x,y]​ 这条边就是割边。lowdfnlowy​dfnx​说明从y 出发在不经过[,][x,y] 这条边的前提下不管怎么走都无法达到x 或更早访问的节点。故删除[,][x,y] 这条边图的联通块一定能增加。反之如果low≤dfnlowy​≤dfnx​则说明y 能绕行其他边到达x 或更早访问的节点那[,][x,y] 就不是割边了。我们也可以知道环内的边割不断。在这里与割点算法做个对比割点算法是满足low≥dfnlowy​≥dfnx​就可以使x 成为割点因为割边算法是判断[,][x,y] 是否是条割边因此在y 不走[,][x,y] 不能到达x那么[,][x,y] 就是割边因此不可以带等号。而割点需要判断去掉点x 后y 能否到达比x 更早访问的点因此可以带等号。cpp#includebits/stdc.husing namespace std;const int N 5010;int n, m, a, b, ans, cnt;int dfn[N], low[N], tim, top;struct edge { int u, v; } bri[N];vectoredge e;vectorint linker[N];bool cmp(edge x, edge y) {if (x.u y.u) return x.v y.v;return x.u y.u;}void add(int a, int b) {e.push_back({a, b});linker[a].push_back(e.size() - 1);}void tarjan(int x, int in_edge) {dfn[x] low[x] tim;for (int j : linker[x]) {int v e[j].v;if (!dfn[v]) {tarjan(v, j);low[x] min(low[x], low[v]);if (low[v] dfn[x]) bri[cnt] {x, v};} else if (j ! (in_edge ^ 1)) low[x] min(low[x], dfn[v]);}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin n m;for (int i 1, a, b; i m; i) {cin a b;add(a, b), add(b, a);}for (int i 1; i n; i) // 可能不连通if (!dfn[i]) tarjan(i, 0);sort(bri 1, bri cnt 1, cmp);for (int i 1; i cnt; i)cout bri[i].u bri[i].v endl;return 0;}边双连通分量eDCC题目边双连通分量。边双连通分量在无向图中极大的不包含割边的连通块称为边双连通分量。如图[1,2,3],[4],[5],[6][1,2,3],[4],[5],[6] 都是边双连通分量。仍然使用 DFS 枚举节点。当枚举到x 时使用邻点更新lowlowx​和dfndfnx​这个前面已经讲过了。不太明白的可以往前看。然后进行边双连通分量的判定若存在lowdfnlowx​dfnx​那么弹出当前栈中在x 之后加入的点和x这些点就构成了一个边双连通分量。cpp#includebits/stdc.husing namespace std;const int N 500010;int n, m, tim, top;int dfn[N], low[N], stk[N];struct edge { int u, v; };vectoredge e;vectorint linker[N];vectorvectorint ans;void add(int a, int b) {e.push_back({a, b});linker[a].push_back(e.size() - 1);}void tarjan(int x, int ine) {dfn[x] low[x] tim;stk[top] x;for (int j : linker[x]) {int v e[j].v;if (!dfn[v]) {tarjan(v, j);low[x] min(low[x], low[v]);} else if (j ! (ine ^ 1))low[x] min(low[x], dfn[v]);}// 以下记录边双联通分量if (dfn[x] low[x]) {vectorint vec;while (1) {int y stk[top--];vec.push_back(y);if (x y) break;}ans.push_back(vec);}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin n m;for (int i 1, a, b; i m; i) {cin a b;add(a, b), add(b, a);}for (int i 1; i n; i)if (!dfn[i]) tarjan(i, 0);cout ans.size() endl;for (auto i : ans) {cout i.size() ;for (int j : i) cout j ;cout endl;}return 0;}点双连通分量vDCC题目点双连通分量。点双连通分量在无向图中极大的不包含割点的连通块称为点双连通分量注一个点也算点双连通分量。如图[1,2,3],[1,4],[4,5],[4,6][1,2,3],[1,4],[4,5],[4,6] 都是点双连通分量。仍然使用 DFS 枚举节点。当枚举到x 时使用邻点更新lowlowx​和dfndfnx​这个前面已经讲过了。不太明白的可以往前看。然后进行点双连通分量的判定若发现割点判定法low≥dfnlowy​≥dfnx​那么当前栈中在y 之后加入的点与x 就构成了一个点双连通分量注x 与y 相连。并且在记录完点双连通分量后把前栈中在y 之后加入的点全部弹出。当然除了上述判定外在遇到单独节点时也把这个点看作一个边双连通分量。cpp#includebits/stdc.husing namespace std;const int N 500010;int n, m, cnt;vectorint linker[N], dcc[N];int dfn[N], low[N], stk[N], tim, top;bool cut[N];void tarjan(int u, int root) {dfn[u] low[u] tim;stk[top] u;if (linker[u].empty()) { // 孤立点dcc[cnt].push_back(u);return;}int child 0;for (int v : linker[u]) {if(!dfn[v]) {tarjan(v, root);low[u] min(low[u], low[v]);if(low[v] dfn[u]) {child;if(u ! root || child 1) cut[u] true;cnt;int x;do {x stk[top--];dcc[cnt].push_back(x);} while (x ! v);dcc[cnt].push_back(u);}}else low[u] min(low[u], dfn[v]);}}int main() {scanf(%d%d, n, m);for(int i 1; i m; i) {int u, v;scanf(%d%d, u, v);if(u v) continue; // 处理自环linker[u].push_back(v);linker[v].push_back(u);}for(int i 1; i n; i)if(!dfn[i]) tarjan(i, i);// 处理孤立点for(int i 1; i n; i) {if(!dfn[i]) {dcc[cnt].push_back(i);}}printf(%d\n, cnt);for(int i 1; i cnt; i) {printf(%d, (int)dcc[i].size());sort(dcc[i].begin(), dcc[i].end());dcc[i].erase(unique(dcc[i].begin(), dcc[i].end()), dcc[i].end());for(int x : dcc[i]) printf( %d, x);puts();}return 0;}SCC 缩点题目缩点。SCC 缩点将一个有向图中的强连通分量合并成一个点组成了一张有向无环图。如图[1,2,3][1,2,3] 作为一个强连通分量缩成点11[4,5][4,5] 作为一个强连通分量缩成点22。SCC 缩点比较简单只要在找出所有强连通分量之后把这些分量看成一个点就可以了。至于本题的做法就是在缩点完毕之后算出新图中每个点的点权值然后跑 DP 就可以了。cpp// Tarjan算法 O(n m)#includebits/stdc.husing namespace std;const int N 10010;int n, m, a, b, ans;vectorint linker[N], ne[N];int dfn[N], low[N], tim, stk[N], vis[N], top, scc[N], cnt;int siz[N], dout[N], w[N], nw[N], f[N];void add(int a, int b) {linker[a].push_back(b);}void tarjan(int x) {dfn[x] low[x] tim;stk[top] x, vis[x] 1; // 将 x 放入栈中for (int v : linker[x]) {if (!dfn[v]) {tarjan(v);low[x] min(low[x], low[v]);} else if (vis[v])low[x] min(low[x], dfn[v]);}if (dfn[x] low[x]) {cnt;while (1) {int y stk[top--];vis[y] 0;scc[y] cnt;siz[cnt];if (x y) break;}}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin n m;for (int i 1; i n; i) cin w[i];for (int i 1, a, b; i m; i) {cin a b;add(a, b);}for (int i 1; i n; i) // 可能不连通if (!dfn[i]) tarjan(i);for (int x 1; x n; x) {nw[scc[x]] w[x];for (int v : linker[x]) {int a scc[x], b scc[v];if (a ! b) ne[a].push_back(b);}}for (int x cnt; x; x--) { // 记住就好只要倒着枚举就可以了if (f[x] 0) f[x] nw[x];for (int v : ne[x])f[v] max(f[v], f[x] nw[v]);}for (int i 1; i cnt; i)ans max(ans, f[i]);cout ans endl;return 0;}eDCC 缩点题目Redundant Paths G。eDCC 缩点将一个无向图中的边双通分量合并成一个点组成了一棵树。如图[1,2,3][1,2,3] 构成点11[4][4] 构成点2​2​。把边双连通分量处理出来之后进行缩点即可。cpp#includebits/stdc.husing namespace std;const int N 5010, M 20010; // 调整数组大小N为节点数M为有向边数int n, m, a, b, cnt, sum;int dfn[N], low[N], dcc[N], stk[N], tim, top, du[N];int bri[M]; // 扩大bri数组大小至Mstruct edge { int u, v; };vectoredge e;vectorint linker[N];void add(int a, int b) {e.push_back({a, b});linker[a].push_back(e.size() - 1);}void tarjan(int x, int ine) {dfn[x] low[x] tim;stk[top] x;for (int j : linker[x]) {int v e[j].v;if (!dfn[v]) {tarjan(v, j);low[x] min(low[x], low[v]);if (low[v] dfn[x])bri[j] bri[j ^ 1] 1; // 标记桥边} else if (j ! (ine ^ 1))low[x] min(low[x], dfn[v]);}if (dfn[x] low[x]) {cnt;while (1) {int y stk[top--];dcc[y] cnt;if (x y) break;}}}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin n m;for (int i 1, a, b; i m; i) {cin a b;add(a, b), add(b, a);}tarjan(1, -1); // 从节点1开始初始入边编号为-1// 计算缩点后度数只遍历偶数索引边每条无向边处理一次for (int i 0; i 2 * m; i 2) {if (bri[i]) { // 当前无向边是桥int u e[i].u, v e[i].v;du[dcc[u]]; // 更新缩点后连通分量的度数du[dcc[v]];}}// 统计叶子节点数度数为1的连通分量for (int i 1; i cnt; i)if (du[i] 1) sum;cout (sum 1) / 2 endl; // 最小加边数return 0;}vDCC 缩点题目由于占时没有找到题目此处不给出代码。不过结合前面的代码那么写出这个板子也不难。vDCC 缩点将一个无向图中的点双通分量合并成一个点组成了一棵树。如图[1,2,3][1,2,3] 构成点11[4][4] 构成点22。