HDU 6370 Werewolf(并查集+dfs) 18年暑假多校赛第六场

讲解博客：http://www.cnblogs.com/curieorz/p/9447454.html

题意：村民只能说真话，狼人“可以”撒谎，每个人说一句话指向出自己之外任意一人身份，问与多少村民和狼人。

思路：1.因为可以有全狼的情况，所以不存在一定是村民的情况。

           2.通过基环树找狼。（具体参见下图，搬运于别人的博客QAQ。。。）

 

    当我们发现有连续个点是有村民的边，如点1，点2，点3，点4，点5，点6；而这些个连续的其中一个点（如图中的点6）有一条狼人边连到了这些个连续的其他的点（如上图连到了点1）。

    此时，我们用反证法可以证明，倘若1号点是村民，则根据村民不会说谎的性质可以判断出1到6号点全是村民，而根据村民不会说谎的性质，只能证明出1号点必为狼人。此时我们同时也可以发现，倘若1号点是狼人，则根据狼人会说谎的性质可知，指向1号点为村民的也必定是狼人。则1，7为狼人

    因此我们的算法雏形就初步显现出来了。

    我们要维护一些连续的村民点，可以用一个并查集进行维护。我们可以将村民边上的两个点不断的用并查集去合并，而当我们遍历狼边的时候，倘若我们发现狼边上的两个点都在一个集合中，则说明必定满足上述的情况，则我们不断遍历这条狼人边所指向的那个结点（如上图的1号点），判断有多少条指向它的村民边即可。（此处我们可以将村民边反向建立，这样可以让我们高效的查询）

以下是自己写的代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef pair<int,int> pii;
vector<pii> wolf;
vector<int> v[N];
int p[N],ans,n;
void init()
{
	for(int i=0;i<=n;i++)v[i].clear(),p[i]=i;
	wolf.clear();
	ans=0;
}
int root(int x){
     while(p[x]!=x) x=p[x];
     return x;
 }
bool same(int a,int b)
{
	return root(a)==root(b);
}
int findf(int a)
{
	if(p[a]==a)
	return p[a];
	else	{
	         p[a]=findf(p[a]);
	         return p[a];
	       }
}
void merge(int c,int d)
{
	int t1=findf(c);
	int t2=findf(d);
	if(t1!=t2)
	{
		p[t2]=t1;
	}
}
void dfs(int a)
{
	int sz=v[a].size();
	for(int i=0;i<sz;i++)
	{
		ans++;
		dfs(v[a][i]);
	}
}
int main()
{
	int t,x;
	char s[20];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
			init();
		for(int i=1;i<=n;i++)
		{
			scanf("%d %s",&x,s);
			if(s[0]=='w')
			{
				wolf.push_back(make_pair(i,x)); 
				
			}else
			{
				v[x].push_back(i); //指向x的所有村民边 
				merge(x,i); 
			}
		}
		int sz=wolf.size(); 
		for(int i=0;i<sz;i++)
		{
			if(same(wolf[i].first,wolf[i].second))//狼边在村民的集合里 
			{
				ans++;
				dfs(wolf[i].second);//遍历这个点 
			}
		}
		printf("0 %d\n",ans);
	}
	return 0;	
}