lessons/参考实现/06-最小与最大生成树/AtCoder-agc064_b.cpp

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

struct DSU {
    vector<int> parent, size;
    explicit DSU(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a; size[a] += size[b];
        return true;
    }
};

struct Edge { int u, v; char color; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (Edge &e : edges) {
        cin >> e.u >> e.v >> e.color;
        --e.u; --e.v;
    }
    string wanted;
    cin >> wanted;

    DSU dsu(n);
    vector<char> chosen(m, false), satisfied(n, false);
    vector<vector<pair<int, int>>> outgoing(n);
    for (int id = 0; id < m; ++id) {
        Edge e = edges[id];
        bool good_u = wanted[e.u] == e.color;
        bool good_v = wanted[e.v] == e.color;
        if (good_u && good_v && dsu.unite(e.u, e.v)) {
            chosen[id] = true;
            satisfied[e.u] = satisfied[e.v] = true;
        } else if (good_u != good_v) {
            int from = good_u ? e.v : e.u;
            int to = good_u ? e.u : e.v;
            outgoing[from].push_back({to, id});
        }
    }

    queue<int> queue;
    for (int v = 0; v < n; ++v) if (satisfied[v]) queue.push(v);
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();
        for (auto [v, id] : outgoing[u]) {
            if (satisfied[v]) continue;
            satisfied[v] = true;
            chosen[id] = true;
            dsu.unite(u, v);
            queue.push(v);
        }
    }
    if (find(satisfied.begin(), satisfied.end(), false) != satisfied.end()) {
        cout << "No\n";
        return 0;
    }
    for (int id = 0; id < m; ++id) {
        if (!chosen[id] && dsu.unite(edges[id].u, edges[id].v)) chosen[id] = true;
    }
    cout << "Yes\n";
    for (int id = 0; id < m; ++id) if (chosen[id]) cout << id + 1 << ' ';
    cout << '\n';
    return 0;
}