Werewolf（缩点）

Werewolf

题意

狼人杀游戏，规定村民不能说假话，狼人可能说假话。

每一个人可以指认别人（除了自己）是村民或者是狼人。

根据这些指证，我们可以得出：

1、x号必为村民；

2、x号必为狼人；

3、x号可能是村民也可能是狼人。

问必为村民的人数和必为狼人的人数。

思路

题解的代码比较妙啊……

首先我们肯定能分析出不可能有必为村民的情况，因为所有人都可能是狼人这样的情况是成立的。

然后，我们又能发现，只有在环中，只存在一个狼人指证，和至少1个村民指证，那么才能确认其中的某一个人是狼人；

我们再通过这些确认的狼人，推出其他指证这些狼人为平民的人必为狼人。

看！代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 100010;
struct node
{
    int to;
    int v;
}g[N];

int vis[N];
int ans[N];
void solve(int id)
{
    vis[id]=1;
    if(g[id].v==1) //我指证别人是村民
    {
        if(!vis[g[id].to]) //指证的人没有被访问过，就要先让他过一下
        {
            solve(g[id].to);
            if(ans[g[id].to]==-1) ans[id]=-1; //我指证的是铁狼，那么我说了谎，我也是狼
            else if(ans[g[id].to]==id) ans[id]=-1; //我指证的人指证回了我，说明有个环，环中有一个狼人指证，那么我就是那个铁狼。
            else ans[id]=ans[g[id].to]; //我也指向我指证的人的指证
        }
        else if(ans[g[id].to]==0) ans[id]=N; //如果有全为村民的环，这里体现为，我最终指证回了一开始的那个人，结果呢，他居然还是没有得到指证的指证的指证……的对象，说明不能确认他，也就是说是全村民环。
        else //访问过啦，但是也不是全是村民
        {
            ans[id]=ans[g[id].to]; //我继续指证
            if(ans[id]==id) ans[id]=-1; //如果……
        }
    }
    else //我指证别人是狼！但是啥都不一定，所以我指证指证。(- -|||)天呐我在说什么。。。
        ans[id]=g[id].to; 
}


int main()
{
    int t,n,x;
    char s[20];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        memset(ans,0,sizeof(ans));

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&g[i].to);
            scanf("%s",s);
            if(s[0]=='w') g[i].v=0;//狼人
            else g[i].v=1;
        }

        for(int i=1;i<=n;i++)
            if(ans[i]==0)
                solve(i);

        int cnt=0;
        for(int i=1;i<=n;i++)
            if(ans[i]==-1)cnt++;

        printf("0 %d\n",cnt);
    }
    return 0;
}