思路与算法

按边编号迭代lowlink求桥，去掉桥后划分边双连通分量，块内若有魔法石边则标记。把桥缩成森林；从起点块到终点块的唯一链上，任一块有标记或任一桥有石头就成功，终点不可达则失败。

正确性说明

桥不可能走后再回，否则重复使用该桥，所以任何合法路线只经过源到终点块的桥链。一个无桥连通块内，给定入口、出口和指定边，可以安排不重复边的路线经过该边：可由连接所需点的无桥子结构或耳分解逐步插入绕行得到。因此链上块内部及桥上的任一石头均可取得，链外石头无法取后返回。

复杂度

每组初始化、求桥、分量划分及森林遍历共O(n+m)时间，O(n+m)空间；T组逐组处理。全部深图遍历使用显式栈。

易错点

跳过父边编号而非父节点，平行边才不会误判为桥。起终点在同一边双块也可能取得石头后返回；只有所在块有石头才成功。不能把普通连通分量上的任意石头都算可达。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> u(m), v(m), c(m);
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < m; i++) {
            cin >> u[i] >> v[i] >> c[i];
            --u[i];
            --v[i];
            g[u[i]].push_back({v[i], i});
            g[v[i]].push_back({u[i], i});
        }
        int src, dst;
        cin >> src >> dst;
        --src;
        --dst;
        vector<int> tin(n), low(n), par(n, -1), pe(n, -1), it(n), bridge(m);
        int tim = 0;
        for (int root = 0; root < n; root++)
            if (!tin[root]) {
                vector<int> st(1, root);
                tin[root] = low[root] = ++tim;
                while (!st.empty()) {
                    int x = st.back();
                    if (it[x] < (int)g[x].size()) {
                        auto ed = g[x][it[x]++];
                        int y = ed.first, id = ed.second;
                        if (id == pe[x])
                            continue;
                        if (!tin[y]) {
                            par[y] = x;
                            pe[y] = id;
                            tin[y] = low[y] = ++tim;
                            st.push_back(y);
                        } else
                            low[x] = min(low[x], tin[y]);
                    } else {
                        st.pop_back();
                        if (par[x] >= 0) {
                            low[par[x]] = min(low[par[x]], low[x]);
                            bridge[pe[x]] = low[x] > tin[par[x]];
                        }
                    }
                }
            }
        vector<int> co(n, -1);
        int cc = 0;
        for (int i = 0; i < n; i++)
            if (co[i] < 0) {
                vector<int> st(1, i);
                co[i] = cc;
                for (int j = 0; j < (int)st.size(); j++)
                    for (auto ed : g[st[j]])
                        if (!bridge[ed.second] && co[ed.first] < 0) {
                            co[ed.first] = cc;
                            st.push_back(ed.first);
                        }
                cc++;
            }
        vector<int> has(cc), prev(cc, -1), flag(cc);
        vector<vector<pair<int, int>>> h(cc);
        for (int i = 0; i < m; i++)
            if (bridge[i]) {
                h[co[u[i]]].push_back({co[v[i]], c[i]});
                h[co[v[i]]].push_back({co[u[i]], c[i]});
            } else
                has[co[u[i]]] |= c[i];
        vector<int> st(1, co[src]);
        prev[co[src]] = co[src];
        flag[co[src]] = has[co[src]];
        for (int j = 0; j < (int)st.size(); j++) {
            int x = st[j];
            for (auto ed : h[x]) {
                int y = ed.first, z = ed.second;
                if (prev[y] < 0) {
                    prev[y] = x;
                    flag[y] = flag[x] | z | has[y];
                    st.push_back(y);
                }
            }
        }
        cout << (prev[co[dst]] >= 0 && flag[co[dst]] ? "YES" : "NO") << '\n';
    }
}