2018 Multi-University Training Contest 6 Werewolf（hdu6370 基环内向树）

Werewolf

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1264    Accepted Submission(s): 349
 

Problem Description

"The Werewolves" is a popular card game among young people.In the basic game, there are 2 different groups: the werewolves and the villagers.

Each player will debate a player they think is a werewolf or not. 

Their words are like "Player x is a werewolf." or "Player x is a villager.".

What we know is :

1. Villager won't lie.

2. Werewolf may lie. 

Of cause we only consider those situations which obey the two rules above. 

It is guaranteed that input data exist at least one situation which obey the two rules above.

Now we can judge every player into 3 types :

1. A player which can only be villager among all situations, 

2. A player which can only be werewolf among all situations.

3. A player which can be villager among some situations, while can be werewolf in others situations.

You just need to print out the number of type-1 players and the number of type-2 players. 

No player will talk about himself.

 

Input

The first line of the input gives the number of test cases T.Then T test cases follow.

The first line of each test case contains an integer N,indicating the number of players.

Then follows N lines,i-th line contains an integer x and a string S,indicating the i-th players tell you,"Player x is a S."

limits:

1≤T≤10

1≤N≤100,000

1≤x≤N

S∈ {"villager"."werewolf"}

 

Output

For each test case,print the number of type-1 players and the number of type-2 players in one line, separated by white space.

 

Sample Input

1

2

2 werewolf

1 werewolf

 

Sample Output

0  0

 

Source

2018 Multi-University Training Contest 6

题目大意：

只有村民和狼人的狼人杀，村民只能说真话，狼人可能说真话也可能说假话，求一定是铁民和铁狼的个数。

解题思路：

官方解释挺清楚的：

首先，“所有人都是狼人”是合法的，所以第一个答案一定是0。 那么我们的任务就是确认有多少人满足存在一种方案使得这个人是村民，其他人就是铁狼了（即为第二个要求输出 的答案） 我们把所有人抽象成点： 1. 对于每句话，建立一条说话的人指向被说的人的一条有向边。 2. 如果该句话为说某人是狼人，就称这条边为狼人边。 暂时不考虑狼人边，把图分成若干联通块，这样每个联通块： 1. 要么点数和边数一致（基环树) 2. 要么点数比边树多1（树） 对于基环树，由于没有狼人边，所以让他们都是村民是合法的，这些人都不是铁狼。 现在对于树，考虑狼人边（有且仅有一条），狼人边是树根连出去的。 1. 如果狼人边指向的是其他联通块： 那么让树中的人都是村民，其他人都是狼人显然也合法。 这些人都不是铁狼。 2. 如果指向树中的某个节点: 如果根是狼人，则其儿子就是狼人，以至于整棵树都是狼人，没有意义。 如果根是村民，则其指向的节点 是铁狼，则以 为根的子树都是铁狼。 而让树中的其它节点为村民，此时合法。 所以树中非 子树的节点都可以是村民。 因此使用记忆化搜索把那些铁狼找出来，统计一下人数就行了。 时间复杂度O（n）。

举个例子：

如图4说1是狼的话那么1和指向他的节点都一定是铁狼，可以用反证法证的：如果1是村民，那么2一定是村民，4也是村民，村民一定说真话，但是四说1是狼，所以1一定是狼，同理5说1是村民，而1是狼，所以5也是狼，以此类推。

代码：

#include<bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 100005
int next1[MAXN],view[MAXN],du[MAXN]; //du记录该节点的入度，next1记录该点指向的下一个节点，view记录狼还是村民 
vector<int>pre[MAXN]; //记录该节点的所有的入度 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){ //初始化 
			pre[i].clear();
			du[i]=0;
			next1[i]=0;
		}
		int num;
		char str[66];
		for(int i=1;i<=n;i++){
			scanf("%d %s",&num,&str);
			next1[i]=num;
			du[num]++;
			pre[num].push_back(i);
			str[0]=='v'?view[i]=0 : view[i]=1; //0代表村民，1代表狼人 
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			int temp=i;
			while(du[temp]==0 && du[next1[temp]]>=1){ //找到环状结构 
				du[temp]--;
				du[next1[temp]]--;
				temp=next1[temp];
			}
		}
		for(int i=1;i<=n;i++){
			int wolf=0;
			int temp=i;
			int index;

			while(du[temp]==1){ 
				du[temp]--;
				if(view[temp]==1)
				{
					wolf++;
					index=next1[temp];
				}
				temp=next1[temp];
			}
			if(wolf==1){ //如果该环刚好有一个人是狼，那么那个人肯定就是狼人 
				ans++;
				int size=pre[index].size();
				queue<int>hh;
				for(int j=0;j<size;j++){ //说这个节点是人的全部都是狼 
					if(view[pre[index][j]]==0)
					hh.push(pre[index][j]);
				}
				while(!hh.empty()){
					int fr=hh.front();
					hh.pop();
					if(view[fr]==0){
						ans++;
						int newsize=pre[fr].size();
						for(int j=0;j<newsize;j++){
							hh.push(pre[fr][j]);
						}
					}
				}
			}
		}
		printf("0 %d\n",ans);
	}
	return 0;
}