johnchen902's Blog

Is there an odd-length simple path between two specified vertices in a given undirected graph?

We would like to transform the graph into a tree with some of the vertices labeled as "stars", such that there is an odd simple path in the graph, iff the corresponding path on the tree has stars on it, or the corresponding path is also odd-lengthed.

First, I found all biconnected components. There are two kinds of biconnected components: one with odd cycles and one without odd cycles.

Either way, remove all edges in the components. For one with odd cycles, create a new "star" node and connect it to other vertices. For one without odd cycles, create a new node connecting to "even" vertices, create another connecting it to "odd" vertices, and finally connect the two new nodes.

After that it's just a classical tree problem. There is another way to solve it. It's faster to code but harder to think. First, find a spanning forest. Then, for each edge not on the forest…

#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <stack>
using namespace std;
struct Dj {
    unordered_map<int, int> a;
    int find(int x) {
        return a.count(x) ? (a[x] = find(a[x])) : x;
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y)
            a[x] = y;
    }
    bool same(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }
};
Dj naive;
vector<int> adj[100000];
void add_edge(int a, int b) {
    naive.merge(2 * a, 2 * b + 1);
    naive.merge(2 * a + 1, 2 * b);
    adj[a].push_back(b);
    adj[b].push_back(a);
}
int depth[100000];
stack<int> torjanstack;
int n2;
vector<int> adj2[200000];
bool isstar[200000];
void handle_bcc(const vector<int> &bcc) {
    Dj dj;
    for(int x : bcc)
        for(int c : adj[x]) {
            dj.merge(2 * x, 2 * c + 1);
            dj.merge(2 * c, 2 * x + 1);
        }

    int ref = bcc.front();
    if(dj.same(2 * ref, 2 * ref + 1)) {
        int star = n2++;
        isstar[star] = true;
        for(int x : bcc) {
            adj2[x].push_back(star);
            adj2[star].push_back(x);
        }
    } else {
        int even = n2++;
        int odd = n2++;
        adj2[even].push_back(odd);
        adj2[odd].push_back(even);
        for(int x : bcc) {
            int y = dj.same(2 * ref, 2 * x) ? even : odd;
            adj2[x].push_back(y);
            adj2[y].push_back(x);
        }
    }
}
int torjan(int x, int p) {
    depth[x] = p == -1 ? 1 : depth[p] + 1;
    int mind = depth[x];
    torjanstack.push(x);
    for(int c : adj[x]) {
        if(c == p)
            continue;
        if(depth[c]) {
            mind = min(mind, depth[c]);
            continue;
        }
        int cd = torjan(c, x);
        if(cd > depth[x]) { // normal edge
            adj2[x].push_back(c);
            adj2[c].push_back(x);
            continue;
        }
        if(cd < depth[x]) { // part of larger bcc
            mind = min(mind, cd);
            continue;
        }
        vector<int> bcc;
        int y;
        do {
            y = torjanstack.top();
            torjanstack.pop();
            bcc.push_back(y);
        } while(y != c);
        bcc.push_back(x);
        handle_bcc(bcc);
    }
    if(mind == depth[x])
        torjanstack.pop();
    return mind;
}
// int n2;
// vector<int> adj2[200000];
// bool isstar[200000];
int depth2[200000];
int anc[200000][18];
bool hasstar[200000][18];
void dfs(int x, int p) {
    if(p == -1) {
        anc[x][0] = x;
        depth2[x] = 1;
    } else {
        anc[x][0] = p;
        depth2[x] = depth2[p] + 1;
    }
    for(int c : adj2[x])
        if(c != p)
            dfs(c, x);
}
void preprocess(int n) {
    n2 = n;
    for(int i = 0; i < n; i++)
        if(depth[i] == 0)
            torjan(i, -1);
    for(int i = 0; i < n2; i++)
        if(depth2[i] == 0)
            dfs(i, -1);
    for(int i = 0; i < n2; i++)
        hasstar[i][0] = isstar[i];
    for(int i = 1; i < 18; i++)
        for(int j = 0; j < n2; j++) {
            int m = anc[j][i - 1];
            anc[j][i] = anc[m][i - 1];
            hasstar[j][i] = hasstar[j][i - 1] || hasstar[m][i - 1];
        }
}
bool query(int a, int b) {
    if(a == b || naive.find(2 * a) != naive.find(2 * b + 1))
        return false;
    if((depth2[a] + depth2[b]) % 2)
        return true;
    if(depth2[a] < depth2[b])
        swap(a, b);
    for(int i = 0; i < 18; i++)
        if((depth2[a] - depth2[b]) & (1 << i)) {
            if(hasstar[a][i])
                return true;
            a = anc[a][i];
        }
    if(a == b)
        return false;
    for(int i = 18 - 1; i >= 0; i--) {
        if(anc[a][i] != anc[b][i]) {
            if(hasstar[a][i] || hasstar[b][i])
                return true;
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return isstar[a] || isstar[b] || isstar[anc[a][0]];
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        add_edge(a, b);
    }
    preprocess(n);
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        puts(query(a, b) ? "Yes" : "No");
    }
}