HDU - 6370 Werewolf 2018 Multi-University Training Contest 6 (DFS找环)

求确定身份的人的个数。

只能确定狼的身份，因为只能找到谁说了谎。但一个人是否是民，无法确定。

将人视作点，指认关系视作边，有狼边和民边两种边。

确定狼的方法只有两种：

　　1. 在一个仅由一条狼边组成的环中，狼边指向的那个点必定是狼。

　　2. 环外指认铁狼为民的也必定是狼。

所以用原图找环求情况1中的铁狼，反向建图找情况2中的狼。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn =1e5+;

const int INF =0x3f3f3f3f;

struct Edge{

    int v;bool w;

};

Edge G[maxn];

vector<Edge> rG[maxn];

int pre[maxn],dfn;

bool isw[maxn];

queue<int> Q;

int res;

void init(int N){

    res=;

    memset(pre,,sizeof(pre));

    memset(isw,,sizeof(isw));

    for(int i=;i<=N;++i) rG[i].clear();

}

void AddEdge(int u,int v,bool w){

    G[u] = (Edge){v,w};

    rG[v].push_back((Edge){u,w});

}

void BFS()

{

    while(!Q.empty()){

        int u = Q.front();Q.pop();

        for(int i=;i<rG[u].size();++i){

            Edge &e =rG[u][i];

            if(!e.w && !isw[e.v]){

                Q.push(e.v);

                isw[e.v] = true;

            }

        }

    }

}

void Tarjan(int u){

    int v;bool w;

    pre[u]=;

    v= G[u].v;

    w = G[u].w;

    if(!pre[v])

        Tarjan(v);

    else if(pre[v]==){                   //找到环

        int cnt=, tar,t;

        for(t=v;;t= G[t].v){

            Edge &e = G[t];

            if(e.w){

                cnt++;

                tar = G[t].v;

            }

            if(e.v==v) break;

        }

        if(cnt==){                    //只有一个狼边才行

            isw[tar] = true;

            Q.push(tar);

        }

    }

    pre[u]=;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.in","r",stdin);

        freopen("1009.out","w",stdout);

    #endif

    int T,N,u,v,tmp;

    char op[];

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        init(N);

        for(int u=;u<=N;++u){

            scanf("%d %s",&v,op);

            if(op[]=='w') AddEdge(u,v,);

            else AddEdge(u,v,);

        }

        for(int i =;i<=N;++i){

            if(!pre[i])

                Tarjan(i);

        }

        BFS();

        for(int i=;i<=N;++i)

            if(isw[i])  res++;

        printf("%d %d\n",,res);

    }

    return ;

}