HDU 6370 狼人杀（并查集）

题目描述：
有n个人在玩狼人杀，每个人有两种身份，狼或者村民，村民必须要将真话，而狼可能讲假话。现在每个人都会说出一个除了自己外的一个人身份，现在问你有多少个人确定是村民，有多少个人确定是狼人。

题目分析：
因为题目不排斥所有玩家都是狼人的情况（这一点都不符合游戏规则好吧），因此题目中所有的人说的所有的话均有可能是假的。因此我们完全无法确定是否有人是村民。但是存在一定是狼人的情况。
当出现一种类似下图的情况：

当我们发现有连续个点是有村民的边，如点1，点2，点3，点4，点5，点6；而这些个连续的其中一个点（如图中的点6）有一条狼人边连到了这些个连续的其他的点（如上图练到了点1）。
此时，我们用反证法可以证明，倘若1号点是村民，则根据村民不会说谎的性质可以判断出1到6号点全是村民，而根据村民不会说谎的性质，只能证明出1号点必为狼人。此时我们同时也可以发现，倘若1号点是狼人，则根据狼人会说谎的性质可知，指向1号点的村民边则必定是狼人。

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef pair<int,int>PLL;
vector<int>human[maxn];
vector<PLL>wolf;
int Far[maxn];
int n;
void init(){//初始化
    for(int i=1;i<=n;i++){
        Far[i]=i;
    }
    wolf.clear();
    for(int i=0;i<=n;i++){
        human[i].clear();
    }
}
int Find_F(int x){//并查集找爸爸
    if(Far[x]==x) return x;
    else return Far[x]=Find_F(Far[x]);
}
void unit(int x,int y){//并查集合并
    x=Find_F(x);
    y=Find_F(y);
    if(x==y) return ;
    else Far[x]=y;
}
bool same(int x,int y){//判断是否在一个集合
    return Find_F(x)==Find_F(y);
}
int ans=0;
void dfs(int x){//dfs找指向该点的村民边
    int len=human[x].size();
    for(int i=0;i<len;i++){
        ans++;
        dfs(human[x][i]);
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        scanf("%d",&n);
        init();
        for(int i=1;i<=n;i++){
            char str[20];
            int op;
            scanf("%d%s",&op,str);
            if(str[0]=='v'){
                human[op].push_back(i);//反向建边
                unit(op,i);
            }
            else{
                wolf.push_back(make_pair(i,op));
            }
        }
        ans=0;
        int sz=wolf.size();
        for(int i=0;i<sz;i++){
            int from=wolf[i].first;
            int to=wolf[i].second;
            if(same(from,to)){
                ans++;
                dfs(to);
            }
        }
        cout<<"0 "<<ans<<endl;
    }
}