题解 | #Puzzle: Wagiri#

输入时将qie存起来，将所有lun使用tarjan进行缩点，最后使用并查集， 将存起来的qie加上，看看是否能将所有点串起来

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

struct Edge{int u, v;};

int n, m;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
vector<int> dcc[N];

vector<Edge> qie;

bool in_ans[M];

int p[N];

vector<Edge> ans;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    p[px] = py;
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u, int from) {
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;
    
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
        } else if (i != (from ^ 1)) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    
    if (dfn[u] == low[u]) {
        dcc_cnt ++;
        int y;
        do {
            y = stk[top --];
            id[y] = dcc_cnt;
            dcc[dcc_cnt].push_back(y);
        } while (y != u);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) h[i] = -1;
    
    for (int i = 1; i <= m; i ++) {
        int u, v; string w;
        cin >> u >> v >> w;
//         cout << u << " " << v << " " << w << endl;
        if (w == "Lun") {
            add(u, v); add(v, u);
        } else if (w == "Qie") { // 先把切边存起来
            qie.push_back((Edge){u, v});
        }
    }
    for (int i = 1; i <= n; i ++)
        if (!dfn[i])
            tarjan(i, -1);

    for (int i = 1; i <= n; i ++)
        if (!id[i]) {
            dcc_cnt ++;
            id[i] = dcc_cnt;
            dcc[dcc_cnt].push_back(i);
        }
    
    bool flag = true;
    
    for (int i = 1; i <= n; i ++) p[i] = i;
    
    for (int idx = 1; idx <= dcc_cnt; idx ++) {
        for (auto u : dcc[idx]) {
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (in_ans[i] || in_ans[i ^ 1] || id[j] != idx) continue;
                in_ans[i] = in_ans[i ^ 1] = true;
                ans.push_back((Edge) {u, j});
                merge(u, j);
            }
        }
    }
    
    for (auto e : qie) {
        if (find(e.u) == find(e.v)) continue;
        ans.push_back(e);
        merge(e.u, e.v);
    }
    
    for (int i = 1; i <= n; i ++)
        if (find(i) != find(1)) 
        {
            flag = false;
            break;
        }
    
    if (flag) {
        cout << "YES" << endl;
        cout << ans.size() << endl;
        for (auto a : ans) {
            cout << a.u << " " << a.v << endl;
        }
    } else {
        cout << "NO" << endl;
    }
//     for (int i = 1; i <= n; i ++) cout << dfn[i] << " " << low[i] << endl;
//     for (int i = 1; i <= n; i ++) {
//         for (int j = h[i]; j != -1; j = ne[j]) {
//             int k = e[j];
//             cout << k << " ";
//         }
//         cout << endl;
//     }
}

int main() {
    int t; t = 1;
    while (t --)
        solve();
}