Codeforces 97E Leaders 点双联通

Leaders

我们随便找一颗生成树出来， 如果询问的两点的距离为奇数则肯定可以， 

否则看两点树上路径中有没有边在一个奇环中， 对于一个点双联通分量来说，

要么没有奇环， 要么两两之间都有奇环， 这个画画图就能知道，

然后求个bcc的过程中处理一下就好了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
using namespace std;

const int N = (int)1e5 + 7;
const int LOG = 17;

int n, m, q;
int depth[N], pa[N][LOG], val[N];
bool odd[N], vis[N];
vector<PII> G[N];

int col[N], col_cnt;
int dfn[N], low[N], dfs_clock;

struct Edge {
    int u, v, id;
};

vector<Edge> E;
Edge estk[N];
int etop;

int fa[N], w[N];

int getRoot(int x) {
    if(fa[x] == x) return x;
    int rt = getRoot(fa[x]);
    w[x] ^= w[fa[x]];
    return fa[x] = rt;
}

bool unite(int u, int v) {
    int x = getRoot(u);
    int y = getRoot(v);
    if(x == y) {
        return !(w[u] ^ w[v] ^ 1);
    }
    else {
        w[y] = w[u] ^ w[v] ^ 1;
        fa[y] = x;
        return true;
    }
}

void tarjan(int u, int eid) {
    dfn[u] = low[u] = ++dfs_clock;
    col[u] = col_cnt;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].se, id = G[u][i].fi;
        if(id == eid) continue;
        if(!dfn[v]) {
            estk[++etop] = Edge{u, v, id};
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                E.clear();
                while(1) {
                    E.push_back(estk[etop--]);
                    if(E.back().id == id) break;
                }
                for(auto &e : E) {
                    fa[e.u] = e.u;
                    fa[e.v] = e.v;
                    w[e.u] = w[e.v] = 0;
                }
                bool flag = true;
                for(auto &e : E) {
                    if(!unite(e.u, e.v)) {
                        flag = false;
                        break;
                    }
                }
                if(!flag) {
                    for(auto &e : E) {
                        odd[e.id] = true;
                    }
                }
            }
        }
        else if(dfn[v] < dfn[u]) {
            estk[++etop] = Edge{u, v, id};
            low[u] = min(low[u], dfn[v]);
        }
    }
}


void dfs(int u, int fa) {
    vis[u] = true;
    depth[u] = depth[fa] + 1;
    pa[u][0] = fa;
    for(int i = 1; i < LOG; i++) {
        pa[u][i] = pa[pa[u][i - 1]][i - 1];
    }
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].se, id = G[u][i].fi;
        if(vis[v]) continue;
        val[v] = val[u] + odd[id];
        dfs(v, u);
    }
}

int getLca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for(int i = LOG - 1; i >= 0; i--) {
        if(d >> i & 1) {
            u = pa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) {
        if(pa[u][i] != pa[v][i]) {
            u = pa[u][i];
            v = pa[v][i];
        }
    }
    return pa[u][0];
}

inline int getDis(int u, int v) {
    int lca = getLca(u, v);
    return depth[u] + depth[v] - 2 * depth[lca];
}
inline int getVal(int u, int v) {
    int lca = getLca(u, v);
    return val[u] + val[v] - 2 * val[lca];
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(mk(i, v));
        G[v].push_back(mk(i, u));
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) {
            col_cnt++;
            tarjan(i, 0);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            dfs(i, 0);
        }
    }
    scanf("%d", &q);
    while(q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        if(col[u] != col[v] || !getVal(u, v) && !(getDis(u, v) & 1)) puts("No");
        else puts("Yes");
    }
    return 0;
}

/*
*/