【MX-X8-T3】「TAOI-3」地地爱打卡题解

Asaha_Akina · 2025-01-31 23:57:28 · 题解

算法标签

图论
深度优先搜索 (DFS)
并查集

题目大意

题目给定一个无向图，图中的每条边连接两个节点。大 Y 同学从节点 s 出发，每走过一条边则能量值加 1，最终希望到达节点 t，并且在此过程中，能量值在经过一定的边后恰好为 0，且快乐值恰好为 x。在图中，大 Y 同学可以选择在某些节点时通过按位异或操作清空他的能量值，并更新他的快乐值。

输入

一个图有 n 个节点和 m 条边。

输出

对于每组查询，输出 "tribool" 如果可以满足条件，否则输出 "expand"。

思路分析

这道题赛时交了五次才过，难度不算特别高，但是需要注意一些特殊情况，请见本部分文末。

连通性

首先我们可以通过深度优先搜索（DFS）来分析图的连通性。对于每个节点，判断其是否为二分图（c[u]）并确定其所属的连通块（b[u]）。

如果节点 s 和 t 不在同一个连通块中，那么直接输出 "expand"。\ 如果在同一连通块中，我们进一步检查节点 s 和 t 的 c 值，以判断是否可以满足要求。

判断图性质

两种状态：我们需要考虑两种情况：
- 如果 c[s] = N，说明该节点不能清空能量值，这时我们检查 x 是否为 0。
- 如果 c[s] = 2，即节点已经清空过能量值（为二分图），我们直接输出 "tribool"。

DFS 和图的染色

通过 DFS 对图进行染色，每个连通块对应一种染色。具体地，使用 c[u] 来表示节点的颜色，b[u] 用于表示所属的连通块。\ 另外，引入变量 k 用于记录 DFS 中每个连通块的节点数。\ 详细见下方代码。

注意

孤立节点：只能原地操作，要求 x=0 且 s=t。(毒瘤)

非二分图：存在奇环，奇偶性可调，总能满足条件。

二分图：检查x的奇偶性是否与路径奇偶性一致。

时间复杂度 O(n + m + q)

参考代码 (100 pts)


//C++
#include <bits/stdc++.h>
#define N 250020
using namespace std;
int n, m, q, c[N], b[N], k;
bool f;
vector<int> G[N];
void search(int u) {
    b[u] = m;
    k++;
    for (int v : G[u]) {
        if (c[v] == -1) {
            c[v] = c[u] ^ 1;
            search(v);
        }
        else if (c[u] ^ c[v] ^ 1) f = 0;
    }
}
void searchDFS(int u) {
    c[u] = 2;
    for (int v : G[u]) {
        if (c[v] != 2) {
            searchDFS(v);
        }
    }
}
void initialize() {
    cin >> n >> m >> q;
    for (int u, v; m--;) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(c, -1, sizeof(c));
    m = 0;
    // 预处理阶段，通过 DFS 进行图的连通块划分
}
void work() {
    for (int i = 1; i <= n; i++) {
        if (c[i] == -1) {
            f = 1;
            c[i] = k = 0;
            m++;
            search(i);
            if (k == 1) {
                c[i] = N;
            }
            if (!f) {
                searchDFS(i);
            }
        }
    }
}
void output() {
    for (int s, t, x; q--;) {
        cin >> s >> t >> x;
        if (b[s] != b[t]) {
            cout << "expand" << endl;
        }
        else if (c[s] == N) {
            cout << (!x ? "tribool" : "expand") << endl;
        }
        else if (c[s] == 2) {
            cout << "tribool" << endl;
        }
        else {
            cout << ((c[s] ^ c[t] ^ x) & 1 ? "expand" : "tribool") << endl;
        }
    }
}
int main() {
    initialize();
    // 预处理阶段，通过 DFS 进行图的连通块划分
    work();
    // 查询阶段，检查每组询问
    output();
    //检查、输出
    return 0;
    //好习惯
}

【MX-X8-T3】「TAOI-3」地地爱打卡 题解