题意是一堆人，从1到n编号，每个人i说一句话，x。x是正数表示i说x君是个好人，x是负数表示i说x君是坏人。问这个群体中最多能有多少好人，把这种情况用字典序的方式输出(好人用A表示，坏人用B表示)，希望我把题意说清楚了。
又做了一道Hackerrank上一道很好玩的题目，做的时候怎么都想不出来。。。
但看完了题解之后，又发现这个题目。。。
其实这个思路以前做并查集的时候有过，就是每个人就两种可能，即每个点就两种状态，那就对每个点再增加一个点，i增加一个点，i+n。这两个点始终都是对立的关系，如果i是好人，那么i+n一定是坏人。当时也想到dfs了，就是想把这个类的人归到一起去，比方说i是好人，i说j是好人，j说k是好人，那么就会希望i、j、k搞到一起去。这个时候就发挥了增加这个点的作用了，i比如是好人，i说j是坏人，那这个意思也就是i说j+n是坏人，i和j+n要搞到一起去，我靠，和并查集的一些题一样啊。。。。
后面就是查各个集的人数，胜利即是正义，人多即是正义。
官方题解代码：
#pragma warning(disable:4996) #include#include #include #include #include #include using namespace std;const int mx = 300003;int n;int norma(int x){ if (x < 0) return abs(x) + n; else return x;}int inv(int x){ x = norma(x); if (x > n) return x - n; else return x + n;}vector g[2 * mx];int kc[mx];int color[mx];int flag[mx];void call(int u, int mar){ if (color[u]) return; color[u] = mar; if (u <= n) kc[mar]++; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; call(v, mar); }}void addedge(int u, int v){ g[u].push_back(v);}int main(){ //freopen("i.txt", "r", stdin); //freopen("o.txt", "w", stdout); int t, u, v, ass; int invu, invt; cin >> t; while (t--) { memset(kc, 0, sizeof(kc)); memset(color, 0, sizeof(color)); cin >> n; for (int i = 1; i <= 2 * n + 1; i++) { g[i].clear(); } for (int i = 1; i <= n; i++) { u = i; cin >> v; v = norma(v); addedge(u, v); addedge(v, u); invu = inv(u); invt = inv(v); addedge(inv(u), inv(v)); addedge(inv(v), inv(u)); } ass = 0; for (int i = 1; i <= n * 2; i++) { if (!color[i]) { ass++; call(i, ass); } } memset(flag, 0, sizeof(flag)); for (int i = 1; i <= n; i++) { u = i; v = inv(i); u = color[u]; v = color[v]; if (!flag[u] && !flag[v]) { if (kc[u] >= kc[v])//查数量，贪心，数量多的为好人 { flag[u] = 1; flag[v] = 2; } else { flag[u] = 2; flag[v] = 1; } } } for (int i = 1; i <= n; i++) { if (flag[color[i]] == 1) cout << "A"; else cout << "B"; } cout << endl; } //system("pause"); return 0;}