LCA+tarjan+桥+dsu
蒟蒻刷到个难题。。。。。。
题目给的图一定是联通的。
我们大致的想法是:先进行缩点。把图变成一个树。节点与节点之间用桥连接。
这并不难,我们tarjan一下,找到桥然后染色就可以了。
然后添加边时。在书上的两个节点之间连一条边。一定会构成一个环。
这个环中原本的边会失去桥的属性。
那么:假设在u和v之间建边。u,v的最近公共祖先为LCA。
那么u->LCA v->LCA 之间的边都不在是桥。
我刚开始的代码是从u和v暴力向上找公共祖先。并一路削除路过的边的桥的属性。
如果,已经是消除过的状态无妨。如果是第一次消除,那么桥的数量就减一。
#include<iostream> #include<algorithm> using namespace std; const int max_n = 1e5 + 100; const int max_m = 2e5 + 100; struct edge{ int to, rev, next; bool vis; }E[max_m << 1]; int head[max_n]; int cnt = 1; void add(int from, int to, int rev, int vis = true) { E[cnt].to = to;E[cnt].vis = vis; E[cnt].next = head[from];E[cnt].rev = rev; head[from] = cnt++; } int dfn[max_n], low[max_n]; int tot = 0; void tarjan(int u,int fa_id) { dfn[u] = low[u] = ++tot; for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (i == fa_id)continue; if (dfn[v] == -1) { tarjan(v, E[i].rev); low[u] = min(low[u], low[v]); if (low[v] > dfn[u])E[i].vis = E[E[i].rev].vis = false; }else low[u] = min(low[u], dfn[v]); } } int fa[max_n]; int cl[max_n]; int cls = 0; int dep[max_n]; void dfs(int u, int color, int p) { fa[color] = p;cl[u] = color;dep[color] = dep[p] + 1; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (cl[e.to] != 0)continue; if (e.vis == false)dfs(e.to, ++cls, color); else dfs(e.to, color, p); } } bool already[max_n]; int LCA(int u,int v) { int res = 0; u = cl[u];v = cl[v]; if (dep[u] < dep[v])swap(u, v); while (dep[u] > dep[v]) { if (!already[u])++res; already[u] = true; u = fa[u]; }while (u != v) { if (!already[u])++res; if (!already[v])++res; already[u] = already[v] = true; u = fa[u];v = fa[v]; }return res; } int N, M, Q; int main() { ios::sync_with_stdio(0); int tcase = 0; while (cin >> N >> M) { if (N == 0 && M == 0)break; fill(head, head + max_n, 0);cnt = 1; fill(dfn, dfn + max_n, -1);tot = 0; fill(already, already + max_n, false); fill(cl, cl + max_n, 0);cls = 0; cout << "Case " << ++tcase << ":\n"; for (int i = 1, u, v;i <= M;++i) { cin >> u >> v; add(u, v, cnt + 1); add(v, u, cnt - 1); }tarjan(1, -1); dfs(1, ++cls, 0); int ans = 0; for (int i = 1;i < cnt;++i) if (!E[i].vis) ++ans; ans >>= 1; cin >> Q; for (int i = 1, u, v;i <= Q;++i) { cin >> u >> v; ans -= LCA(u, v); cout << ans << endl; }cout << endl; } }
但,仔细想想。这种做法复杂度很高。
因为,万一我们的树退化成链表。然后Q次查询全部都是首和尾。
此时最坏的情况将是O(n*q)看下数据10^8。。。被放过了。
如何优化这个算法。利用并查集,也就是说,我们在树上也进行缩点。
将u->LCA v->LCA一路上的点都并入LCA.
同时,在找LCA时代码也有所不同了。很是巧妙。
#include<iostream> #include<algorithm> using namespace std; const int max_n = 1e5 + 100; const int max_m = 2e5 + 100; struct edge{ int to, rev, next; bool vis; }E[max_m << 1]; int head[max_n]; int cnt = 1; void add(int from, int to, int rev, int vis = true) { E[cnt].to = to;E[cnt].vis = vis; E[cnt].next = head[from];E[cnt].rev = rev; head[from] = cnt++; } int dfn[max_n], low[max_n]; int tot = 0; void tarjan(int u,int fa_id) { dfn[u] = low[u] = ++tot; for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (i == fa_id)continue; if (dfn[v] == -1) { tarjan(v, E[i].rev); low[u] = min(low[u], low[v]); if (low[v] > dfn[u])E[i].vis = E[E[i].rev].vis = false; }else low[u] = min(low[u], dfn[v]); } } int fa[max_n]; int cl[max_n]; int cls = 0; int dep[max_n]; void dfs(int u, int color, int p) { fa[color] = p;cl[u] = color;dep[color] = dep[p] + 1; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (cl[e.to] != 0)continue; if (e.vis == false)dfs(e.to, ++cls, color); else dfs(e.to, color, p); } } int par[max_n]; int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); } int LCA(int u,int v) { int res = 0; u = cl[u];v = cl[v]; int uu = find(u);int vv = find(v); while (uu != vv) { if (dep[uu] > dep[vv]) { par[uu] = find(fa[uu]); uu = find(fa[uu]); ++res; } else if (dep[vv] > dep[uu]) { par[vv] = find(fa[vv]); vv = find(fa[vv]); ++res; } else { par[uu] = find(fa[uu]); uu = find(fa[uu]); par[vv] = find(fa[vv]); vv = find(fa[vv]); ++res;++res; } }return res; } int N, M, Q; int main() { ios::sync_with_stdio(0); int tcase = 0; while (cin >> N >> M) { if (N == 0 && M == 0)break; for (int i = 0;i < max_n;++i)par[i] = i; fill(head, head + max_n, 0);cnt = 1; fill(dfn, dfn + max_n, -1);tot = 0; fill(cl, cl + max_n, 0);cls = 0; cout << "Case " << ++tcase << ":\n"; for (int i = 1, u, v;i <= M;++i) { cin >> u >> v; add(u, v, cnt + 1); add(v, u, cnt - 1); }tarjan(1, -1); dfs(1, ++cls, 0); int ans = 0; for (int i = 1;i < cnt;++i) if (!E[i].vis) ++ans; ans >>= 1; cin >> Q; for (int i = 1, u, v;i <= Q;++i) { cin >> u >> v; ans -= LCA(u, v); cout << ans << endl; }cout << endl; } }