建立网站tk,网络营销实务教案,杭州蒙特网站建设,做水果生意去那个网站文章目录 定义Tarjan求e-DCCTarjan求v-DCC395. 冗余路径1183. 电力396. 矿场搭建 定义
无向图有两种双连通分量
边双连通分量#xff0c;e-DCC点双连通分量#xff0c;v-DCC
桥#xff1a;删除这条无向边后#xff0c;图变得不连通#xff0c;这条边被称为桥 边双连通分… 文章目录 定义Tarjan求e-DCCTarjan求v-DCC395. 冗余路径1183. 电力396. 矿场搭建 定义
无向图有两种双连通分量
边双连通分量e-DCC点双连通分量v-DCC
桥删除这条无向边后图变得不连通这条边被称为桥 边双连通分量极大的不含有桥的连通区域说明无论删除e-DCC中的哪条边e-DCC依旧连通 该连通分量的任意边属于原图中的某条环。此外任意两点之间一定包含两条不相交无公共边的路径
割点删除该点与该点相关的边后图变得不连通这个点被称为割点 点双连通分量极大的不含有割点的连通区域
一些性质
每个割点至少属于两个连通分量任何两个割点之间的边不一定是桥任何桥两边的端点不一定是割点两者没有必然联系一个点连通分量也不一定是边连通分量 Tarjan求e-DCC
无向图不存在横叉边 和有向图的强连通分量类似引入dfn和low两个数组 如何找到桥判断x-y的y是否能走到x之前祖先节点如果能走到x和y在一个环中删除这条边其他点依然是连通的 所以x-y为桥dfn[x] low[y]
如何找到所有边的双连通分量
删除所有桥或者用stk辅助若dfn[x] low[x]说明x出发一定走不到x的祖先节点那么x和其父节点之间的边是桥此时还在stk中的点为e-DCC的节点
这里使用第二种方式模板
void tarjan(int x, int from)
{dfn[x] low[x] tp;stk[ tt] x;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y, i);low[x] min(low[x], low[y]);}else if (i ! (from ^ 1))low[x] min(low[x], dfn[y]);if (dfn[x] low[y])st[i] st[i ^ 1] true;}if (dfn[x] low[x]){int y;cnt ;do {y stk[tt -- ];id[y] cnt;} while (x ! y);}
}由于无向图要存储两条有向边并且从数组的0下标开始存储所以01、23…这样一对的边是互相反向的边即i和i ^ 1为反向边 为什么与有向图的强连通分量不同边双连通分量不需要使用st数组以标记栈中的元素 因为无向图不存在横叉边的概念就不会出现x-y而y的dfn小于x因为在无向图中y一定会向x遍历 Tarjan求v-DCC
如何求割点low[y] dfn[x]删除x节点后y就是一颗独立的子树
如果x不是根节点那么x是一个割点如果x是根节点至少有两个y满足以上关系
求割点的板子
void tarjan(int x)
{dfn[x] low[x] tp;int t 0;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y);low[x] min(low[x], low[y]);if (low[y] dfn[x]) t ;}else low[x] min(low[x], dfn[y]);}if (x ! root) t ;ans max(ans, t);
}将每个v-DCC向其包含的割点连一条边 缩点后边的数量不会增加点的数量可能会增加到两倍
tarjan求v-DCC与割点的板子 一个孤立的点也是一个v-DCC这里需要特判 若满足条件low[y] dfn[x]那么y的子树与x一起就是一个v-DCC 对于该节点是否是割点还需要特判若该节点为根并且与该节点相连的连通块数量为1那么该节点就不是一个割点
void tarjan(int x)
{dfn[x] low[x] tp;stk[ tt ] x;if (x root h[x] -1){ dcnt;dcc[dcnt].push_back(x);return;}int t 0; // 与x相连的连通块数量for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y);low[x] min(low[x], low[y]);if (low[y] dfn[x]){dcnt , t ;if (x ! root || t 1) st[x] true; // x为割点int u;do {u stk[tt -- ];dcc[dcnt].push_back(u);} while (u ! y);dcc[dcnt].push_back(x);}}else low[x] min(low[x], dfn[y]);}
}395. 冗余路径
395. 冗余路径 - AcWing题库
任意两点间都存在两条没有重复边的路径等价于整个图是一个双连通分量
将无向连通图的边双连通分量缩点后得到的结构是一颗树因为边双连通分量是不包含桥的结构缩点后图中只含有桥即删除任意一条边后图成为两个连通块这是一个树结构
为了满足题意需要向这颗树中添加边使之成为边连通分量那么要加几条边
连接所有叶子节点使这颗树结构成为双连通分量至少需要加 [ ( c n t 1 ) / 2 ] [(cnt 1) / 2] [(cnt1)/2]然后再下取整的边数也就是将每个叶子节点相连使环满足双连通分量的性质
注意cnt为1时需要特判
#include iostream
#include cstring
using namespace std;const int N 5010, M 10010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt, id[N];
bool st[N]; int d[N];
int n, m;void add(int x, int y)
{e[idx] y, ne[idx] h[x], h[x] idx ;
}void tarjan(int x, int from)
{dfn[x] low[x] tp;stk[ tt] x;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y, i);low[x] min(low[x], low[y]);if (dfn[x] low[y])st[i] st[i ^ 1] true;}else if (i ! (from ^ 1))low[x] min(low[x], dfn[y]);}if (dfn[x] low[x]){int y;cnt ;do {y stk[tt -- ];id[y] cnt;} while (x ! y);}
}int main()
{memset(h, -1, sizeof(h));scanf(%d%d, n, m);int x, y;for (int i 0; i m; i ){scanf(%d%d, x, y);add(x, y), add(y, x);}tarjan(1, -1);for (int i 0; i idx; i )if (st[i])d[id[e[i]]] ;int res 0;for (int i 1; i cnt; i )if (d[i] 1) res ;if (cnt 1) puts(0);else printf(%d\n, (res 1) / 2);return 0;
}debug^的优先级小于!
可以不使用st数组标记桥
#include iostream
#include cstring
using namespace std;const int N 5010, M 10010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt, id[N];
int d[N];
int n, m;void add(int x, int y)
{e[idx] y, ne[idx] h[x], h[x] idx ;
}void tarjan(int x, int from)
{dfn[x] low[x] tp;stk[ tt] x;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y, i);low[x] min(low[x], low[y]);}else if (i ! (from ^ 1))low[x] min(low[x], dfn[y]);}if (dfn[x] low[x]){int y;cnt ;do {y stk[tt -- ];id[y] cnt;} while (x ! y);}
}int main()
{memset(h, -1, sizeof(h));scanf(%d%d, n, m);int x, y;for (int i 0; i m; i ){scanf(%d%d, x, y);add(x, y), add(y, x);}tarjan(1, -1);for (int x 1; x n; x )for (int i h[x]; i ! -1; i ne[i]){int y e[i];int a id[x], b id[y];if (a ! b) d[a] ;}int res 0;for (int i 1; i cnt; i )if (d[i] 1) res ;if (cnt 1) puts(0);else printf(%d\n, (res 1) / 2);return 0;
}1183. 电力
1183. 电力 - AcWing题库
枚举所有割点判断删除哪个割点后剩余的连通块数量最大 剩余的连通块数量为ans cnt - 1 由于题目给定的图并不是一个连通图所以可能存在多个连通块cnt为连通块数量 枚举所有割点只能在一个连通块中枚举此时其他连通块的数量为cnt - 1 又因为ans为删除割点后剩余连通块最多的值所以答案为ans cnt - 1
这题的点编号从0开始
#include iostream
#include cstring
using namespace std;const int N 10010, M 30010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int ans, n, m, root;void add(int x, int y)
{e[idx] y, ne[idx] h[x], h[x] idx ;
}void tarjan(int x)
{dfn[x] low[x] tp;int t 0;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y);low[x] min(low[x], low[y]);if (low[y] dfn[x]) t ;}else low[x] min(low[x], dfn[y]);}if (x ! root) t ;ans max(ans, t);
}int main()
{while (scanf(%d%d, n, m), n | m){memset(h, -1, sizeof(h));memset(dfn, 0, sizeof(dfn));idx tp cnt ans 0;int x, y;for (int i 0; i m; i ){scanf(%d%d, x, y);add(x, y), add(y, x);}for (root 0; root n; root){if (!dfn[root]) {cnt ;tarjan(root);}}printf(%d\n, ans cnt - 1);}return 0;
}debugdfn数组没有置空 396. 矿场搭建
396. 矿场搭建 - AcWing题库 对于图中的每个连通块分情况讨论
若连通块无割点那么任意设置两个救援点即可若连通块中有割点缩点将每个割点依然看成一个点将每个v-DCC向其包含的割点连线
缩点后得到一棵树对于叶子节点需要建立救援点。因为只有一个点与其相连若该点坍塌需要在内部建立救援点。假设内部节点数量为cnt方案数为cnt-1个去除割点对于非叶子节点无需建立救援点因为无论与之相连的哪个割点坍塌该节点都能走到叶子节点而叶子节点已经建立救援点
#include iostream
#include cstring
#include vector
using namespace std;typedef unsigned long long ULL;
const int N 1010, M 1010;
int h[N], e[M], ne[M], idx;
vectorint dcc[N];
int dcnt, root;
int dfn[N], low[N], tp;
int stk[N], tt;
bool st[N];
int n, m;void add(int x, int y)
{e[idx] y, ne[idx] h[x], h[x] idx ;
}void tarjan(int x)
{low[x] dfn[x] tp;stk[ tt ] x;if (x root h[x] -1){dcnt ;dcc[dcnt].push_back(x);return;}int t 0;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!dfn[y]){tarjan(y);low[x] min(low[x], low[y]);if (low[y] dfn[x]){t , dcnt ;if (x ! root || t 1) st[x] true;int u;do {u stk[tt -- ];dcc[dcnt].push_back(u);} while (u ! y);dcc[dcnt].push_back(x);}}else low[x] min(low[x], dfn[y]);}
}int main()
{int T 1;while (scanf(%d, m), m){for (int i 0; i N; i ) dcc[i].clear();memset(h, -1, sizeof(h));memset(dfn, 0, sizeof(dfn));memset(st, false, sizeof(st));tp dcnt idx tt n 0;for (int i 0; i m; i ){int x, y;scanf(%d%d, x, y);add(x, y), add(y, x);n max(n, x), n max(n, y);}for (root 1; root n; root )if (!dfn[root]) tarjan(root);ULL sum 1; int ans 0;for (int i 1; i dcnt; i ){int t 0;for (int j 0; j dcc[i].size(); j )if (st[dcc[i][j]]) t ;if (t 0) {if (dcc[i].size() 1) ans 2, sum * ((ULL)dcc[i].size() * (dcc[i].size() - 1)) / 2;else ans ;}else if (t 1) ans 1, sum * (dcc[i].size() - 1);}printf(Case %d: %d %llu\n, T , ans, sum);}return 0;
}debug由于多组测试数据没有初始化干净所有元素 最后统计救援点数量以及方案总数时没有对孤立点进行特判
