HDU6370：Werewolf 推理+拓扑排序 2018第六场杭电多校

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.".

他们的话就像“玩家x是狼人”。或“玩家x是村民。”

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 :

现在我们可以判断每个玩家分为3种类型： 1. A player which can only be villager among all situations, 1.在所有情况下都只能成为村民的玩家 2. A player which can only be werewolf among all situations. 2.在所有情况下都只能成为狼人的玩家。 3. A player which can be villager among some situations, while can be werewolf in others situations. 3.在某些情况下可以成为村民的玩家，而在其他情况下可以是狼人。

You just need to print out the number of type-1 players and the number of type-2 players. 你只需要打印出1型球员的数量和2型球员的数量 。 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

题意：传送门

• 一个以狼人杀为背景的游戏(hhh)。题目保证村民一定说真话，狼人可能说真话也可能说假话。 n(n≤ 100000)个人，每个人人指认另一个人的身份，为狼或村民。问你能确定多少个人一定是村民，多少个人一定是狼。

思路：

贼有意思的一道题，打比赛时和同学一起讨论了很多情况，终于有了思路，最后大神抬了一手，终AC。

思路大概是这样的：

一：任何情况都不能确定谁一定是村民！

因为有狼这个不定因素。狼的话可真可假，也就是说可能所有人都是狼！这样也不会出现矛盾。

二：A认为B是村民，B认为A是狼。这时A一定是狼！

在草稿纸列举出两个人互相指认的4种情况，只有这一种情况能确定被指认是狼的这个人一定是狼。

反证法：

如果A是村民，A就会说真话，则B也是村民，继续可得出结论A是狼，矛盾！故这种情况下A一定是狼！

以此类推可得：只有当1认为2是村民，2认为3是村民，3认为4是村民...n−1认为n是村民，n认为i(1≤i≤n−1)是狼时，可以确定i一定是狼！(省略号里全部是指认下一个人为村民)

有了这个谬论可以大胆敲代码。 若A指认B，就A向B连边。就把边标号，指认是狼就把边标号为1.

然后找环，当存在这样一个有向环，环中只有一条标号为1的边，则那个被指认为狼的人一定是狼！

只要我们能确定一个人是狼，那么逆推，认为这个人是村民的人也肯定是狼！

我的解法是先拓扑排序给访问过的点打标记。未被打标记的点一定是环上的点。

然后dfs跑环检查那个狼的突破口。最后逆推出所有狼。

当然确定环还有别的方法，tarjan也行，并查集也行等等。

自此，本题结束。QwQorz~~~

AC代码：

#include<bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = 100005;
struct lp{
    int v,w,nex,id;
}cw[N*10],rev[N*10];//正向图和反向图的链式前向星
int n;
int revhead[N];
int head[N],tot;
int in[N];//入度
int vis[N], cnt[N];//是否被访问过
int is[N];//是否是狼
void init(){//初始化函数
  mme(head,-1);mme(in,0);
  mme(revhead,-1);mme(cnt,0);mme(is,0);
  tot=-1;
}
void add_edge(int u,int v,int id){//加边
  cw[++tot].v=v;cw[tot].nex=head[u];cw[tot].id=id;
  head[u]=tot;
  rev[tot].v=u;rev[tot].nex=revhead[v];rev[tot].id=id;
  revhead[v]=tot;
}
void tuopu(){//拓扑排序只是为了找出环
  queue<int>Q;
  for(int i=1;i<=n;++i){
    if(in[i]==0){
      Q.push(i);
    }
  }
  mme(vis,0);
  while(!Q.empty()){
    int u = Q.front();Q.pop();
    vis[u]=1;
    for(int i=head[u];~i;i=cw[i].nex){
      int v = cw[i].v;
      in[v]--;
      if(in[v]==0){
        Q.push(v);
      }
    }
  }
}
void dfs(int u,int Fa){//反着搜索找出所有的狼
  is[u]=1;
  for(int i=revhead[u];~i;i=rev[i].nex){
    int v = rev[i].v,id=rev[i].id;
    if(id==0){//id为0表示认为他是村民。而认为狼是村民的人肯定是狼
      dfs(v,u);
    }
  }
}
int num,p;
void find(int u,int Fa){//找出一定是狼的突破点
  cnt[u]=1;
  for(int i=head[u];~i;i=cw[i].nex){
    int v = cw[i].v,id=cw[i].id;
    num+=cw[i].id;
    if(id==1)p=v;//被指向的人是狼
    if(vis[v]==0&&cnt[v]==0){//跑环上的点且未被访问过
      find(v,u);
    }
  }
}
int main(){
  int T, a, c;
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    init();
    char s[15];
    for(int i = 1; i <= n; i++) {
      c=0;
      scanf("%d%s",&a,s);
      if(s[0]=='w')c=1;//给边标号，指认狼的边标号为1
      add_edge(i,a,c);
      in[a]++;
    }
    tuopu();
    for(int i=1;i<=n;++i){
      if(vis[i]==0&&cnt[i]==0){//跑环找肯定是狼的突破点
        num=0;
        find(i,0);
        if(num==1)is[p]=1;//只能有一条边为指认狼，被指向的人是狼
      }
    }
    for(int i=1;i<=n;++i){
      if(is[i]==1){//反着搜索找出所有的狼
        dfs(i,0);
      }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
      ans+=is[i];
    }
    printf("0 %d\n", ans);
  }
  return 0;
}