2018 Multi-University Training Contest 6--HDU 6370 Werewolf（dfs+并查集）

题意：

两种角色：狼和村民；狼的话可真可假，村民的话一定为真。找出铁狼和人的数量。

题解：

因为狼会说谎，所以人的个数是无法确定的。又因为人是说真话，如果他说A是狼，则A一定是狼。

那么我们就可以得到：A说B是人，B说C是人，C说B是狼，这样我们就可以知道B和A一定是狼，因为如果C是狼则全都没有意义，所以C不是狼，那么他说了真话，则B是狼，这时候A说了假话，那他也一定是狼。

#include <algorithm>
#include  <iostream>
#include   <cstdlib>
#include   <cstring>
#include    <cstdio>
#include    <string>
#include    <vector>
#include    <bitset>
#include     <stack>
#include     <cmath>
#include     <deque>
#include     <queue>
#include      <list>
#include       <set>
#include       <map>
#define mem(a) memset(a, 0, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;

const int maxn = 1e6+10;
struct node{
	int id, sayWolf;
}man[maxn];

int Dad[maxn], markWolf[maxn];
vector<int> behindPeople[maxn];

int findDad(int x){
	if(x == Dad[x]){
		return x;
	}
	else{
		return Dad[x] = findDad(Dad[x]);
	}
}

void youIsMyDad(int x, int y){
	int p = findDad(x);
	int q = findDad(y);
	if(p != q){
		Dad[p] = Dad[q];
	}
}

void dfs(int x){
	markWolf[x] = 1;
	if(behindPeople[x].size() == 0){
		return;
	}
	int len = behindPeople[x].size();
	for(int i = 0; i < len; i++){
		dfs(behindPeople[x][i]);
	}
}

int main(){
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t++){
       	int n;
       	scanf("%d", &n);
       	for(int i = 1; i <= n; i++){
       		Dad[i] = i;
       		behindPeople[i].clear();
		}
		for(int i = 1; i <= n; i++){
			char s[15];
			int m;
			scanf("%d %s", &m, s);
			man[i].id = m;
			if(strcmp(s, "werewolf") == 0){
				man[i].sayWolf = 1;
			}
			else{
				man[i].sayWolf = 0;
				youIsMyDad(i, m);
				behindPeople[m].push_back(i);
			}
		}
		mem(markWolf);
		for(int i = 1; i <= n; i++){
			if(man[i].sayWolf == 1){
				int x = man[i].id;
				if(findDad(x) == findDad(i)){
					dfs(x);
				}
			}
		}
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			if(markWolf[i]){
				cnt++;
			}
		}
		printf("0 %d\n", cnt);
    }
}