dw做的网站链接,关键词分析软件,东莞网站开发技术公司电话,做网站需要交管理费吗题意 给一个连通的无向图#xff0c;有两种询问#xff1a; \(a, b, c, d\)#xff0c;问如果删掉\(c,d\)之间的边#xff0c;\(a,b\)之间是否还连通\(a, b, c\)#xff0c;问如果删掉顶点\(c\)#xff0c;\(a,b\)之间是否还连通分析 首先DFS一遍求出进入节点的时间戳\(p…题意 给一个连通的无向图有两种询问 \(a, b, c, d\)问如果删掉\(c,d\)之间的边\(a,b\)之间是否还连通\(a, b, c\)问如果删掉顶点\(c\)\(a,b\)之间是否还连通分析 首先DFS一遍求出进入节点的时间戳\(pre(u)\)离开节点的时间戳\(post(u)\)以及当前节点的子树中能连接到的最小的DFS序\(low(u)\)。 然后预处理一下\(u\)的\(2^i\)级祖先方便计算\(u\)的任意级祖先。 考虑第一种查询 不妨设\(c\)是\(d\)的儿子节点如果\(c,d\)之间是一个桥并且\(a,b\)两个节点一个在\(c\)的子树中一个不在这种情况下是不连通的。 其他情况都是连通的。 考虑第二种查询 分成三种情况讨论 \(a,b\)都在子树\(c\)中如果\(a,b\)在\(c\)的同一个儿子子树中那么去掉\(c\)是连通的。 否则让\(a,b\)往上跳变成\(c\)的两个儿子。如果\(low(a) \geq pre(c)\)或\(low(b) \geq pre(c)\)有一个成立那么是不连通的。\(a,b\)只有一个在子树\(c\)中由于对称性不妨假设\(a\)在子树\(c\)中。 同样让\(a\)往上跳变成\(c\)的儿子。如果\(low(a) \geq pre(c)\)那么不连通否则连通。\(a,b\)都不在子树\(c\)中那么去掉\(c\)完全没有任何影响所以还是连通的。#include cstdio
#include cstring
#include algorithm
using namespace std;const int maxn 100000 10;
const int maxm 1000000 10;struct Edge
{int v, nxt;Edge() {}Edge(int v, int nxt): v(v), nxt(nxt) {}
};int ecnt, head[maxn];
Edge edges[maxm];void AddEdge(int u, int v) {edges[ecnt] Edge(v, head[u]); head[u] ecnt;edges[ecnt] Edge(u, head[v]); head[v] ecnt;
}int n, m;int fa[maxn], dep[maxn];
int dfs_clock, pre[maxn], post[maxn], low[maxn];
bool isbridge[maxn], iscut[maxn];void dfs(int u) {bool flag false;int child 0;pre[u] low[u] dfs_clock;for(int i head[u]; ~i; i edges[i].nxt) {int v edges[i].v;if(v fa[u] !flag) { flag true; continue; }child;if(!pre[v]) {fa[v] u;dep[v] dep[u] 1;dfs(v);low[u] min(low[u], low[v]);if(low[v] pre[u]) {iscut[u] true;if(low[v] pre[u]) isbridge[v] true;}} else low[u] min(low[u], pre[v]);}if(u 1 child 1) iscut[u] false;post[u] dfs_clock;
}int anc[maxn][20];void preprocess() {memset(anc, 0, sizeof(anc));for(int i 1; i n; i) anc[i][0] fa[i];for(int j 1; (1 j) n; j)for(int i 1; i n; i) if(anc[i][j-1])anc[i][j] anc[anc[i][j-1]][j-1];
}int upward(int u, int x) {for(int i 0; i 20; i)if((x i) 1) u anc[u][i];return u;
}int insubtree(int u, int v) {if(pre[v] pre[u] pre[u] post[v]) return 1;return 0;
}bool juedgeVertex(int a, int b, int c) {int in1 insubtree(a, c);int in2 insubtree(b, c);if(in1 in2) {a upward(a, dep[a] - dep[c] - 1);b upward(b, dep[b] - dep[c] - 1);if(a b) return true;if(low[a] pre[c]) return false;if(low[b] pre[c]) return false;}if(in1 ^ in2) {if(!in1) swap(a, b);a upward(a, dep[a] - dep[c] - 1);if(low[a] pre[c]) return false;}return true;
}int main()
{while(scanf(%d%d, n, m) 2) {ecnt 0;memset(head, -1, sizeof(head));while(m--) {int u, v;scanf(%d%d, u, v);AddEdge(u, v);}dfs_clock 0;memset(pre, 0, sizeof(pre));memset(isbridge, false, sizeof(isbridge));memset(iscut, false, sizeof(iscut));dfs(1);preprocess();int q;scanf(%d, q);while(q--) {int op, a, b, c, d;scanf(%d%d%d%d, op, a, b, c);bool ok true;if(op 1) {scanf(%d, d);if(dep[c] dep[d]) swap(c, d);int in1 insubtree(a, c);int in2 insubtree(b, c);if(isbridge[c] (in1 ^ in2) 1) ok false;} else {ok juedgeVertex(a, b, c);}printf(%s\n, ok ? yes : no);}}return 0;
} 转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/5361919.html
