暴力算法

有一个比较显然的暴力算法：考虑奇数和偶数长度两种情况，用 BFS 进行同色扩展即可完成。但是复杂度较高，需要实质上 \(\Theta(n^2 + m^2)\) 的时间进行 BFS。

优化思路

这题的 nb 之处在于其优化思路。这道题的优化思路非常的自然。我们发现瓶颈在于 \(m^2\)，那么我们是否能在不影响答案的情况下，删掉一堆边、删到 \(n\) 级别然后做同样的暴力算法呢？

当然是可以的。首先，我们忽略图中的异色边，只关注同色边。假设忽略这些边之后分成了若干个连通块。考虑连通块的特性，如果这个连通块是个二分图的话，那么不存在奇环。在这个题里面没有奇环是一个很重要的性质，因为如果你想在一个全是同色边的连通块里删边，你必须保证对应的偶环和奇环必须都存在，要不然会影响答案。

回到二分图上，如果是个二分图我们可以随便取一个生成树即可，因为二分图的生成树也是二分图嘛。

如果不是二分图，说明我们要造的新图必须奇环、偶环都要存在，所以我们可以加一个自环来进行调节即可。

再加上那些异色边，就可以得到一张性质和原来图相同的、边级别在 \(\Theta(n)\) 的图了。之后尽情暴力即可。

代码

// P5292.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050, MAX_M = 1e6 + 200;

typedef pair<int, int> pii;

int n, m, q, col[MAX_N], head[MAX_N], current, ui[MAX_M], vi[MAX_M], mem[2][MAX_N];
bool tag[MAX_N], travel[MAX_N][MAX_N], already[MAX_N];
char str[MAX_N];
queue<pii> pool;

struct edge
{
    int to, nxt;
} edges[MAX_M << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

int find(int id, int x) { return mem[id][x] == x ? x : mem[id][x] = find(id, mem[id][x]); }

void dfs(int u, int color)
{
    col[u] = color;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (col[edges[i].to] == 0)
            dfs(edges[i].to, -color);
        else if (col[edges[i].to] == color)
            tag[abs(color)] = true;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%s", &n, &m, &q, str + 1);
    for (int i = 1; i <= n; i++)
        mem[0][i] = mem[1][i] = i, travel[i][i] = true, pool.push(make_pair(i, i));
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &ui[i], &vi[i]);
        if (str[ui[i]] == str[vi[i]])
            addpath(ui[i], vi[i]), addpath(vi[i], ui[i]);
    }
    for (int i = 1; i <= n; i++)
        if (col[i] == 0)
            dfs(i, i);
    memset(head, -1, sizeof(head)), current = 0;
    for (int i = 1; i <= m; i++)
    {
        int u = ui[i], v = vi[i];
        if (str[u] != str[v])
        {
            if (find(0, u) == find(0, v))
                continue;
            addpath(u, v), addpath(v, u);
            mem[0][find(0, u)] = find(0, v);
        }
        else
        {
            if (find(1, u) == find(1, v))
                continue;
            addpath(u, v), addpath(v, u);
            mem[1][find(1, u)] = find(1, v), pool.push(make_pair(u, v));
        }
    }
    for (int i = 1; i <= n; i++)
        if (tag[abs(col[i])] == true && already[abs(col[i])] == false)
            already[abs(col[i])] = true, addpath(i, i);
    // then we get to bfs;
    while (!pool.empty())
    {
        pii u = pool.front();
        pool.pop();
        for (int i = head[u.first]; i != -1; i = edges[i].nxt)
            for (int j = head[u.second]; j != -1; j = edges[j].nxt)
                if (str[edges[i].to] == str[edges[j].to] && travel[edges[i].to][edges[j].to] == false)
                    travel[edges[i].to][edges[j].to] = travel[edges[j].to][edges[i].to] = true, pool.push(make_pair(edges[i].to, edges[j].to));
    }
    while (q--)
    {
        int u, v;
        scanf("%d%d", &u, &v), puts(travel[u][v] ? "YES" : "NO");
    }
    return 0;
}