dfs + 并查集
因为题目不限制狼人的数量,所以无法确定村民有多少个。。因为每一局都有可能全是狼人。。
所以我们要计算的只有一定是狼的数量。
我们把每个玩家当成节点,在一个村民链中,如果该链与一条狼边形成一个环,那么可以推理出这条狼边指向的节点一定是狼。
因为村民不可能说谎,如果假设这条狼边指向的人是村民,那么绕一圈回来他自己就变成狼了,如果这条狼边指向的人是狼,那么在他说真话的情况下他是狼,说假话的情况下也一定是狼了,因为只有狼才说假话。
那么我们又可以进一步推出,说该玩家是村民的人也是狼。
现在思路就很明确了,对于狼边,我们连边,并用并查集维护,对于村民边,我们连反向边。
最后再遍历所有的两边,当狼边的两个节点都在一个集合里时,说明出现了村民链与一条狼边成环的情况,dfs一遍村民的反向边统计狼人数量。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 200005;
int _, n, head1[N], head2[N], cnt1, cnt2, k, parent[N], ans;
char s[20];
bool vis[N];
struct Edge { int v, next; }vi[N<<1], wf[N<<1];
void build(){
full(head1, -1), full(head2, -1);
cnt1 = cnt2 = ans = 0;
for(int i = 0; i <= n; i ++) parent[i] = i;
full(vis, false);
}
void wfInser(int a, int b){
wf[cnt1].v = b, wf[cnt1].next = head1[a], head1[a] = cnt1 ++;
}
void viInser(int a, int b){
vi[cnt2].v = b, vi[cnt2].next = head2[a], head2[a] = cnt2 ++;
}
int find(int p){
while(p != parent[p]){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
bool isConnect(int p, int q){
return find(p) == find(q);
}
void merge(int p, int q){
int pRoot = find(p), qRoot = find(q);
if(pRoot == qRoot) return;
parent[pRoot] = qRoot;
}
void dfs(int s){
vis[s] = true;
for(int i = head2[s]; i != -1; i = vi[i].next){
int u = vi[i].v;
if(vis[u]) continue;
ans ++, dfs(u);
}
}
int main(){
for(_ = read(); _; _ --){
n = read(), build();
for(int i = 1; i <= n; i ++){
scanf("%d%s", &k, s);
if(s[0] == 'w'){
wfInser(i, k), wfInser(k, i);
}
else{
if(isConnect(k, i)) continue;
merge(k, i), viInser(k, i);
}
}
for(int i = 0; i < cnt1; i += 2){
int u = wf[i].v, v = wf[i ^ 1].v;
if(isConnect(u, v)){
if(vis[u]) continue;
ans ++, dfs(u);
}
}
printf("0 %d\n", ans);
}
return 0;
}