C++ 实现正直者和欺诈者判定算法

#include #include

using namespace std;

const int MAXN = 100005; int n, q, f[MAXN];

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

int main() { cin >> n; for (int i = 1; i <= n; i++) { char c; cin >> c; if (c == 'H') f[i] = i; else f[i] = 0; } cin >> q; while (q--) { int x, y; cin >> x >> y; if (find(x) == find(y)) cout << 'Honest' << endl; else cout << 'Lie' << endl; } return 0; }