穿越沙漠

https://www.matiji.net/exam/dohomework/8695/1

题干

题目描述

小码哥准备出一趟远门，今天他经过了一个沙漠。

沙漠中存在 n 个城市和 m 条道路，每条道路连接两个不同的城市。小码哥穿过一条道路的时间恰为半天。也就是说，当小码哥在白天从一个城市出发去相连的城市时，总会在晚上到达；反之在晚上出发总会在白天到达。

小码哥不想浪费多余的时间，因此他到达一个城市后必须立刻出发去下一个城市。为了更好地规划路线，小码哥现在提出了 q 个旅行计划，希望你帮助他判断一下计划的可行性。

具体来说，每个计划中包含出发城市 u 和出发时间（白天/晚上），以及到达城市 v 和到达时间（白天/晚上）。问题是，是否存在一条满足出发、到达时间的从 u 到 v 的路径。

输入格式

第一行包含两个整数 n, m（ $1 \leq n, m \leq 10^5$ ），表示城市个数和道路条数；

接下来 m 行，每行包含两个整数 u, v（ $1 \leq u, v \leq n$ ），表示一条道路连接的两个城市。保证输入不存在重边和自环；

接下来输入一个整数 Q（ $1 \leq Q \leq 10^5$ ），表示询问个数；

然后输入 Q 行，每行包含四个整数 u, v, p, q（ $1 \leq u, v \leq n，p, q \in \{0,1\}$ ），表示一个询问——小码哥希望在时间 p 从城市 u 出发，在时间 q 到达城市 v。p, q 为 0 表示白天，1 表示晚上。

输出格式

对于每个询问，输出 YES 或 NO，表示是否存在满足条件的路径。

思路

显然是图论问题。如果是一次查询，显然直接 bfs 二染色即可。注意，问题是存在性问题，不是找最短路，数组只用于防环。

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(n, vector<int>());
    for(int _ = 0; _ < m; ++_) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    int q; cin >> q;
    while(q--) {
        int u, v, p, pp;
        cin >> u >> v >> p >> pp;
        --u; --v;
        int offset = (p != pp);
        int cur_off = 0;
        vector<char> vis0(n, false);
        vector<char> vis1(n, false);
        queue<int> q;
        q.push(u);
        bool flag = false;
        while(!q.empty()) {
            int s = q.size();
            if(flag) break;
            while(s--) {
                int f = q.front();
                q.pop();
                if(
                    (cur_off == 0 && vis0[f]) ||
                    (cur_off == 1 && vis1[f])
                ) {
                    continue;
                }

                if(cur_off == 0) {
                    vis0[f] = true;
                } else {
                    vis1[f] = true;
                }

                if(cur_off == offset && f == v) {
                    flag = true;
                    break;
                }          

                for(auto e: edges[f]) {
                    q.push(e);
                }
            }
            cur_off = !cur_off;
        }
        if(flag) {
            cout << "yes" << "\n";
        } else {
            cout << "no" << "\n";
        }
    }
    return 0;
}

但是看一下复杂度，必然要离线。离线后对于一个查询有三种情况，

两个城市不在同一个连通块，直接输出 no
两个城市在同一个联通块，且这个联通块有奇数环（即非二分图），直接输出 yes
两个城市在同一个联通块，且这个联通块可二分。基于颜色判断 yes 或 no

代码

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> parent;
    UnionFind(int n) : parent(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[y] = x;
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    UnionFind uf(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        uf.unite(u, v);
    }

    vector<int> color(n, -1);
    vector<bool> is_bipartite(n, true);
    vector<bool> visited(n, false);

    for (int u = 0; u < n; ++u) {
        int root = uf.find(u);
        if (visited[root]) continue;
        visited[root] = true;
        queue<int> q;
        q.push(root);
        color[root] = 0;
        bool bipart_ok = true;
        vector<int> component;
        component.push_back(root);
        while (!q.empty() && bipart_ok) {
            int v = q.front();
            q.pop();
            for (int neighbor : adj[v]) {
                if (uf.find(neighbor) != root) {
                    continue;
                }
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    color[neighbor] = color[v] ^ 1;
                    component.push_back(neighbor);
                    q.push(neighbor);
                } else {
                    if (color[neighbor] == color[v]) {
                        bipart_ok = false;
                        break;
                    }
                }
            }
        }
        for (int node : component) {
            is_bipartite[node] = bipart_ok;
            if (!bipart_ok) {
                color[node] = -1;
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int u, v, p, qq;
        cin >> u >> v >> p >> qq;
        --u; --v;
        if (uf.find(u) != uf.find(v)) {
            cout << "no\n";
            continue;
        }
        if (!is_bipartite[uf.find(u)]) {
            cout << "yes\n";
        } else {
            int desired = (qq - p) % 2;
            if (desired < 0) desired += 2;
            int actual = (color[u] != color[v]) ? 1 : 0;
            if (desired == actual) {
                cout << "yes\n";
            } else {
                cout << "no\n";
            }
        }
    }

    return 0;
}

题干​

思路​

代码​

题干

思路

代码