Network

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;
    }
}