讲解博客: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;
}