双连通分量模板（连通分量例子）

双连通分量模板（连通分量例子）

边双连通分量（一般配上缩点、并查集） tot = 1; void add(int x,int y) { nextt[++tot] = head[x]; head[x] = tot; to[tot] = y; from[tot] = x; } void tarjan(int u) { pre[u] = low[u] = ++dfs_clock; for (int i = head[u];i;i = nextt[i]) { if (i == (bian[u] ^ 1)) continue; int v = to[i]; if (!pre[v]) { bian[v] = i; tarjan(v); if (low[v] < low[u]) low[u] = low[v]; if (low[v] > pre[u]) flag[bian[v]] = flag[bian[v] ^ 1] = 1; } else if (pre[v] < low[u]) low[u] = pre[v]; } } int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } for (int i = 2; i <= tot; i += 2) if (!flag[i]) fa[find(to[i])] = find(from[i]); 参考例题：传送门 点双连通分量： void dfs(int u,int fa) { pre[u] = low[u] = ++dfs_clock; int child = 0; for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (!pre[v]) { node temp; temp.u = u; temp.v = v; e[++top] = temp; child++; dfs(v,u); low[u] = min(low[u],low[v]); if (low[v] >= pre[u]) { iscut[u] = 1; num++; while (1) { int tu = e[top].u,tv = e[top--].v; if (belong[tu] != num) belong[tu] = num; if (belong[tv] != num) belong[tv] = num; if (tu == u && tv == v) break; } } } else if (pre[v] < pre[u] && v != fa) { node temp; temp.u = u; temp.v = v; e[++top] = temp; low[u] = min(low[u],pre[v]); } } if (child == 1 && fa == -1) iscut[u] = 0; } 参考例题：传送门

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。