题面

题目链接

大秦 为你打开 题目传送门

备用题面

一个无向图中有n顶点和m条边，无重边无自环。顶点从1到n编号。

Q次询问，每次询问u,vu,v之间是否存在一条长度为奇数的简单路径。

注：简单路径为不经过重复的点的路径。

思路

我们思考如何才能有一个长度为奇数的简单路径：

  1. 本来就有
  2. 有奇环。

为什么说是有奇环呢？不是说不能经过重复点吗？这里指的其实是经过的路径上有奇环，因为奇环可以分成两边走，由于是奇环，所以两边的奇偶性一定不一样，这样就给了我们选择路径奇偶性的余地。

那么本来就有是什么情况呢？如果两个点在一个 Dfs 生成树上面的深度奇偶性不同，那么他们就属于本来就有奇数路径。因为这样的话 $u\rightarrow root\rightarrow v$ 这样的路径一定是奇数的简单路径。那么如果奇偶性一样怎么办，那么我们就只能指望于两个点到他们 LCA 的路径上有奇环了。不难发现只要至少有一个奇环我们就是可以的。那么就只需要另外处理一个倍增数组，记录这里奇环的数量就可以了。

那么处理奇环也很简单，Tarjan 做点双连通分量，一个没有割点的图绝对有环，我们只需要判断是不是奇环，然后用倍增统计即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m, Q;
Graph G;

inline void Input() {
    read(n, m);
    int u, v;
    for(int i = 1; i <= m; i++) {
        read(u, v);
        G.AddEdge(u, v), G.AddEdge(v, u);
    }
    read(Q);
}

int clc[N], CSG;
int low[N], dfn[N], cntd;
int dep[N];
int vise[M];
int stk[N], top;
int stc[N], topc;
int st[N][20], va[N][20];
int az[N], re[N];

inline void Tarjan(int u, int fa) {
    low[u] = dfn[u] = ++cntd;
    clc[u] = CSG;
    dep[u] = dep[fa] + 1;
    for(int i = G.head(u); i ; i = G.nt(i)) {
        if(vise[(i + 1) / 2]) continue;
        int savetop = top, v = G.to(i);
        stk[++top] = (i + 1) / 2;
        vise[(i + 1) / 2] = 1;
        if(!dfn[v]){
            st[v][0] = u;
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v]>=dfn[u]) {
                int oddHuan = 0;
                topc = 0;
                int v = 0;
                while(top > savetop) {
                    v = stk[top];
                    oddHuan |= az[v];
                    if(!re[G.to(v * 2)]) {
                        stc[++topc] = G.to(v * 2);
                        re[G.to(v * 2)] = 1;
                    }
                    if(!re[G.to(v * 2 - 1)]) {
                        stc[++topc] = G.to(v * 2 - 1);
                        re[G.to(v * 2 - 1)] = 1;
                    }
                    top--;
                }
                for(int j = 1; j <= topc; j++) {
                    if(oddHuan && re[st[stc[j]][0]]) {
                        va[stc[j]][0] = 1;
                    }
                }
                for(int j = 1; j <= topc; j++) {
                    re[stc[j]] = 0;
                }
            }
        }
        else {
            low[u] = min(low[u], low[v]);
            if (dep[v] % 2 == dep[u] % 2) {
                az[(i + 1) / 2] = 1;
            }
        }
    }
}

inline bool LCA(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int flag = 0;
    for(int i = 19; i >= 0; i--) {
        if(dep[st[u][i]] >= dep[v]) {
            flag += va[u][i];
            u = st[u][i];
        }
    }
    if(u == v) {
        return flag;
    }
    for(int i = 19; i >= 0; i--) {
        if(st[u][i] != st[v][i]) {
            flag += va[u][i], u = st[u][i];
            flag += va[v][i], v = st[v][i];
        }
    }
    flag += va[u][0], u = st[u][0];
    flag += va[v][0], v = st[v][0];
    return flag;
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) {
            CSG++;
            Tarjan(i, 0);
        }
    }
    for(int i = 1; i < 20; i++) {
        for(int u = 1; u <= n; u++) {
            st[u][i] = st[st[u][i - 1]][i - 1];
            va[u][i] = va[st[u][i - 1]][i - 1] + va[u][i - 1];
        }
    }
    int u, v;
    while(Q--) {
        read(u, v);
        if(clc[u] != clc[v]) {
            printf("No\n");
            continue;
        }
        if(dep[u] % 2 != dep[v] % 2 || LCA(u, v)) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}