一群人在玩狼人杀，村民只会说真话，狼人会说真话和假话，要你求出那些人一定是村民或者那些人一定是狼人。想到了并查集不会用...
1，如果全部人都是狼人，一定可以所以一定是村民的人一定是0。
2，
加入是这样的话，A说B人，B说C是人，C说D是人，D说B是狼，明显B错误了，这时候假设A是人，那么BCD都是人，矛盾了，所以A不可能是人，所以A是狼。接下来如果B是人，CD也是人，还是矛盾了，所以B是狼。而CD是人不会矛盾，所以可以得到CD可能是人而AB一定是狼。
所以计算的时候我就可以把人用并查集并起来，把狼信息先保留起来，然后最后的时候遍历一遍狼的信息，如果狼对应的两个人在一个集合内，那么久一定有狼存在，也就是狼指向的点和所以指向这个人的点，然后用DFS找出所有的人。这样就可以找出所有一定是狼的点了。
#include<map> #include<set> #include<ctime> #include<cmath> #include<stack> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define lowbit(x) (x & (-x)) typedef unsigned long long int ull; typedef long long int ll; typedef unsigned int ui; const double pi = 4.0*atan(1.0); const int inf = 0x3f3f3f3f; const int maxn = 100010; const int maxm = 100010; const int mod = 1<<30; const double eps = 1e-8; using namespace std; int n, m; int T, tol; int tol1, tol2; struct Node { int u, v; int next; }; struct Edge { int u, v; }; Edge edge[maxn]; Node node[maxn]; int head[maxn]; bool vis[maxn]; int fa[maxn]; int ans; void init() { tol1 = tol2 = 0; ans = 0; memset(fa, -1, sizeof fa); memset(vis, 0, sizeof vis); memset(node, 0, sizeof node); memset(edge, 0, sizeof edge); memset(head, -1, sizeof head); } void addnode(int u, int v) { node[tol1].u = u; node[tol1].v = v; node[tol1].next = head[u]; head[u] = tol1++; } int find(int x) { return fa[x] == -1 ? x : fa[x] = find(fa[x]); } void bind(int u, int v) { int x = find(u); int y = find(v); if(x != y) fa[y] = x; return ; } void dfs(int u) { for(int i=head[u]; ~i; i=node[i].next) { int v = node[i].v; if(vis[v]) continue; vis[v] = true; ans++; dfs(v); } } int main() { scanf("%d", &T); while(T--) { init(); scanf("%d", &n); m = n; char op[20]; int id; for(int i=1; i<=m; i++) { scanf("%d %s", &id, op); if(op[0] == 'w') { tol2++; edge[tol2].u = i; edge[tol2].v = id; } else { addnode(id, i); bind(id, i); } } for(int i=1; i<=tol2; i++) { int u = edge[i].u; int v = edge[i].v; if(find(u) != find(v)) continue; ans++; vis[v] = true; dfs(v); } printf("0 %d ", ans); } return 0; }