HDU6370（思维+搜索

题意：

现在有N个人，每个人要么是第一类：说的全是真话；要么是第二类：说的可能是假话。

每一个人x都指认另一个人y是第一类或第二类人。

请问在所有合法的情况下，有多少人必定是第一类人、有多少人必定是第二类人？

思路：（首先题解送上

当然其实没怎么懂。。我也不是这么写的

主要点：

然后再xjb补充一下吧，以防以后看不懂（反正都是别的博客上截来的

 

反正我的写法就是找出所有的环，判断这个环中是不是只有一条狼边，如果只有一条狼边，那么将这条狼边指向的那个点赋为铁狼，如果大于1那么这个环上所有点都可能是村民。最后再Dfs一遍判断环外的点

最后代码（三个dfs可以说是十分丑陋了。。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int to[100000+10],v[100000+10],ans[100000+10],f,num,p,vis[100000+10];
void dfs(int rt,int pos)//找环
{
    vis[rt]=pos;
    if(vis[to[rt]]==0)
    {
        dfs(to[rt],pos);
    }
    else
    {
        if(vis[to[rt]]==pos) f=rt;
        else f=-1;
        return;
    }
}
void DFS(int rt,int ed)//记录环的狼边数，并记录指向结点
{
    ans[rt]=1;
    if(v[rt]==1){num++;p=to[rt];}
    if(to[rt]==ed)return;
    DFS(to[rt],ed);
}
void Dfs(int rt)//判断环外的其他点
{
    if(ans[to[rt]]==0) Dfs(to[rt]);
    if(v[rt]==0&&ans[to[rt]]==2)
    {
        ans[rt]=2;
        return;
    }
    else ans[rt]=1;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof vis);
        memset(ans,0,sizeof ans);
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;
            char s[10];
            scanf("%d%s",&x,s);
            to[i]=x;
            if(s[0]=='w') v[i]=1;
            else v[i]=0;
        }
        int tot=1;
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                dfs(i,tot);
                tot++;
                if(f!=-1)
                {
                    num=0;
                    DFS(f,f);
                    if(num==1) ans[p]=2;
                }
            }
        }
        for(int i=1;i<=n;i++)//判断环外的其他点
        {
            if(!ans[i]) Dfs(i);
        }
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            if(ans[i]==2) sum++;
        }
        printf("0 %d\n", sum);
    }
    return 0;
}
/*
10
6
2 w
3 v
4 w
5 v
6 v
2 v

*/