Werewolf
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1381 Accepted Submission(s): 386
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.".
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 :
1. A player which can only be villager among all situations,
2. A player which can only be werewolf among all situations.
3. A player which can be villager among some situations, while can be werewolf in others situations.
You just need to print out the number of type-1 players and the number of type-2 players.
No player will talk about himself.
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"}
解析 题解说的还是比较明白的，村名的数量一定是0 存在铁狼只有一种情况 (狼人边指向树中某个节点）
思路就是 找所有 除了根节点指出的边是狼人边 其他节点指出的边都是好人边组成的基环树 狼人边所指的那个子树大小就是铁狼的数量
比如 2，3，1，4，5，6 是满足条件的 基环树 铁狼的个数就是 sz[4]=4 (方框指向的是另一个联通块 所以不存在铁狼）
只有n条边 并查集 dfs 标记什么的 搞一搞 就过了
AC代码 写的太丑了
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl;
using namespace std;
typedef long long ll;
const ll maxn=1e5+,inf=1e18;
const ll mod=1e9+;
vector<pair<int,int> > g[maxn],gg[maxn];
int vis[maxn],sz[maxn];
int par[maxn];
int _find(int x)
{
return x==par[x]?x:par[x]=_find(par[x]);
}
void unio(int a,int b)
{
int ra=_find(a);
int rb=_find(b);
if(ra!=rb)
par[rb]=ra;
}
void dfs2(int x)//把 子树的大小求出来 并且把树归到一个集合
{
sz[x]=;vis[x]=;
for(int i=;i<gg[x].size();i++)
{
pair<int,int> it=gg[x][i];
if(vis[it.fi]==)
{
dfs2(it.fi);
}
unio(x,it.fi);
sz[x]+=sz[it.fi];
}
}
char s[];
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int temp1,temp2;
for(int i=;i<=n;i++)
{
g[i].clear(),gg[i].clear();
par[i]=i;
vis[i]=sz[i]=;
}
for(int i=;i<=n;i++)
{
scanf("%d%s",&temp1,s);
if(s[]=='w')temp2=;
else temp2=;
g[i].pb(mp(temp1,temp2));
if(temp2==)
gg[temp1].pb(mp(i,temp2));
}
int ans=;
for(int i=;i<=n;i++)
{
if(vis[i]==&&gg[i].size()>)//没被访问过 且有子节点
dfs2(i);
}
for(int i=;i<=n;i++)
{
if(_find(g[i][].fi)==_find(i)&&g[i][].se==)//指出的是狼边 且狼边指向自己所在的树
ans+=sz[g[i][].fi];
}
printf("0 %d\n",ans);
}
} //4 v 1
//1 v 2
//1 v 3
//5 v 4
//6 v 5
//4 w 6
//4 w 7
//6 v 8
//10
//8
//4 v
//1 v
//1 v
//5 v
//6 v
//4 w
//4 w
//6 v