Submission #44580627

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
int nEdge = 1;
struct edge {
    int x, y, id;
    char color;
    friend istream & operator >> (istream &in, edge &A) {
        in >> A.x >> A.y >> A.color;
        A.id = nEdge++;
        return in;
    }
};
const int NM = 2e5 + 5;
int n, m, par[NM], sz[NM];
edge e[NM];
char s[NM];
vector<edge> t[3];
vector<int> ans;
bool ok[NM];
void init() {
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        sz[i] = 1;
    }
}
int find_set(int u) {
    return par[u] == u ? u : par[u] = find_set(par[u]);
}
bool union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return false;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return true;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> e[i];
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= m; ++i) t[(s[e[i].x] != e[i].color) + (s[e[i].y] != e[i].color)].push_back(e[i]);
    init();
    for (edge &i: t[0]) if (union_set(i.x, i.y)) {
        ok[i.x] = ok[i.y] = 1;
        ans.push_back(i.id);
    }
    for (edge &i: t[1]) {
        if (s[i.y] == i.color) swap(i.x, i.y);
        if (ok[i.x]) continue;
        if (union_set(i.x, i.y)) {
            ok[i.x] = 1;
            ans.push_back(i.id);
        }
    }
    bool check = 1;
    for (int i = 1; i <= n; ++i) check &= ok[i];
    if (!check) {
        cout << "No";
        return 0;
    }
    for (int i = 1; i <= m; ++i) if (union_set(e[i].x, e[i].y)) ans.push_back(i);
    cout << "Yes\n";
    for (int &i: ans) cout << i << " ";
}

Submission Info

Judge Result