管道

题目链接：LOJ 2788

题目大意

给你一个 n 个点 m 条边的无向图不一定连通，把每个连通块看做子图，求每一个子图的桥。
n 1e5 m 6e6 空间 16 MB

思路

发现存不下所有的边，但是能存点。
那考虑能不能在一棵生成树上面搞。

那对于一条非树边，它会让树上的一条路径上的边都不会是桥边。
那你把所有非树边都这么限制一下，最后还没有被否决的就是桥边了。

那至于怎么限制，一个想法是树上差分，那就需要找到 LCA。
那你可以二次读入数据，第一次先把生成树建出来，然后弄个树链剖分或者倍增预处理，然后第二次处理非树边，求出 LCA 打标记。
然后最后从下往上，把标记加上去，然后每个点判断一下它跟它父亲的边就行了。

那这样的复杂度是 O(n+qlog⁡n)O(n+q\log n)O(n+qlogn)，大概有 606060 左右，而且二次读入很慢。
（不过开 O2，再加上加速 cin cout 的 ios::sync_with_stdio(false)勉强能在 LOJ 卡过）

考虑瓶颈是啥，是你非树边太多了，一个一个打标记都不太行。
而且需要预处理才能得到 LCA。
（虽然有个 O(nlog⁡n−1)O(n\log n-1)O(nlogn−1) LCA，但是似乎有更好的方法）

注意到非树边这么多，比树边还多，真的全有用吗。
会发现当非树边出现环之类的时候，你可以在环上任意选一条边不要，它的贡献是其他边能拼凑出来的。
也就是说，你其实只需要保留非树边的一棵生成树。

那这个时候非树边的数量也降到了 O(n)O(n)O(n)，我们甚至就可以直接在第一次读入的时候存下所有的非树边，也就不需要二次读入，复杂度也降到了可以通过的 O(nα(n)log⁡n)O(n\alpha(n)\log n)O(nα(n)logn)
（当然你可以用 O(nlog⁡n−1)O(n\log n-1)O(nlogn−1) 的 LCA 做到 O(nα(n))O(n\alpha(n))O(nα(n))）

代码

不需要二次读入数据

#include
#include
#include
#include
#includeusing namespace std;const int N = 1e5 + 100;
int n, m, fa[N], x, y, Fa[N], le[N], KK, a[N], lca;
vector  > out;
struct node {int to, nxt;
}e[N << 1];void add(int x, int y) {e[++KK] = (node){y, le[x]}; le[x] = KK;e[++KK] = (node){x, le[y]}; le[y] = KK;
}int find(int now) {if (fa[now] == now) return now;return fa[now] = find(fa[now]);
}int Find(int now) {if (Fa[now] == now) return now;return Fa[now] = Find(Fa[now]);
}struct SLPF {int fa[N], son[N], top[N], deg[N], dfn[N];void dfs0(int now, int father) {top[now] = 1; deg[now] = deg[father] + 1; fa[now] = father;for (int i = le[now]; i; i = e[i].nxt)if (e[i].to != father) {dfs0(e[i].to, now); top[now] += top[e[i].to];if (top[e[i].to] > top[son[now]]) son[now] = e[i].to;}}void dfs1(int now, int father) {dfn[now] = ++dfn[0];if (son[now]) {top[son[now]] = top[now]; dfs1(son[now], now);}for (int i = le[now]; i; i = e[i].nxt)if (e[i].to != father && e[i].to != son[now]) {top[e[i].to] = e[i].to; dfs1(e[i].to, now);}}int LCA(int x, int y) {while (top[x] != top[y]) {if (deg[top[x]] < deg[top[y]]) swap(x, y);x = fa[top[x]];}if (deg[x] > deg[y]) swap(x, y);return x;}void find(int now, int father) {dfn[now] = 1;for (int i = le[now]; i; i = e[i].nxt)if (e[i].to != father) {find(e[i].to, now);a[now] += a[e[i].to];}if (!a[now] && father) printf("%d %d\n", now, father);}
}T;int re; char c;
int read() {re = 0; c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') {re = (re << 3) + (re << 1) + c - '0';c = getchar();}return re;
}int main() {
//	freopen("read.txt", "r", stdin);n = read(); m = read();for (int i = 1; i <= n; i++) fa[i] = Fa[i] = i;for (int i = 1; i <= m; i++) {x = read(); y = read();if (find(x) != find(y)) {add(x, y);fa[find(x)] = find(y);}else if (Find(x) != Find(y)) {Fa[Find(x)] = Find(y);out.push_back(make_pair(x, y));}}for (int i = 1; i <= n; i++) if (!T.top[i]) T.dfs0(i, 0);for (int i = 1; i <= n; i++) if (!T.dfn[i]) T.top[i] = i, T.dfs1(i, 0);for (int i = 0; i < out.size(); i++) {x = out[i].first; y = out[i].second;lca = T.LCA(x, y);a[x]++; a[y]++; a[lca] -= 2;}for (int i = 1; i <= n; i++) T.dfn[i] = 0;for (int i = 1; i <= n; i++) if (!T.dfn[i]) T.find(i, 0);return 0;
}

勉强卡过的二次读入数据

#include
#include
#includeusing namespace std;const int N = 1e5 + 100;
int n, m, fa[N], x, y, lca, a[N];int find(int now) {if (fa[now] == now) return now;return fa[now] = find(fa[now]);
}struct SLPF {struct node {int to, nxt;}e[N << 1];int fa[N], son[N], top[N], le[N], KK, deg[N], dfn[N];void add(int x, int y) {e[++KK] = (node){y, le[x]}; le[x] = KK;e[++KK] = (node){x, le[y]}; le[y] = KK;}void dfs0(int now, int father) {top[now] = 1; deg[now] = deg[father] + 1; fa[now] = father;for (int i = le[now]; i; i = e[i].nxt)if (e[i].to != father) {dfs0(e[i].to, now); top[now] += top[e[i].to];if (top[e[i].to] > top[son[now]]) son[now] = e[i].to;}}void dfs1(int now, int father) {dfn[now] = ++dfn[0];if (son[now]) {top[son[now]] = top[now]; dfs1(son[now], now);}for (int i = le[now]; i; i = e[i].nxt)if (e[i].to != father && e[i].to != son[now]) {top[e[i].to] = e[i].to; dfs1(e[i].to, now);}}int LCA(int x, int y) {while (top[x] != top[y]) {if (deg[top[x]] < deg[top[y]]) swap(x, y);x = fa[top[x]];}if (deg[x] > deg[y]) swap(x, y);return x;}void find(int now, int father) {dfn[now] = 1;for (int i = le[now]; i; i = e[i].nxt)if (e[i].to != father) {find(e[i].to, now);a[now] += a[e[i].to];}if (!a[now] && father) printf("%d %d\n", now, father);}
}T;int main() {
//	freopen("read.txt", "r", stdin);ios::sync_with_stdio(false);cin >> n >> m;for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= m; i++) {cin >> x >> y;if (find(x) != find(y)) {T.add(x, y);fa[find(x)] = find(y);}}for (int i = 1; i <= n; i++) if (!T.top[i]) T.dfs0(i, 0);for (int i = 1; i <= n; i++) if (!T.dfn[i]) T.top[i] = i, T.dfs1(i, 0);cin.clear(); cin.seekg(0, ios::beg);cin >> n >> m;for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= m; i++) {cin >> x >> y;if (find(x) != find(y)) {fa[find(x)] = find(y);}else {lca = T.LCA(x, y);a[x]++; a[y]++; a[lca] -= 2;}}for (int i = 1; i <= n; i++) T.dfn[i] = 0;for (int i = 1; i <= n; i++) if (!T.dfn[i]) T.find(i, 0);return 0;
}