HDU 6370(思维)-蒲公英云

HDU 6370(思维)

传送门

思路：因为狼说什么都是可以的，所以全是狼是可以，村民为0。

那问题就是转化成求铁狼的数量。我们对村民边建图，我们发现，一个连通分量要么是个基环树，要么是个树。对于基环树全是村民的话显然成立。所以不存在铁狼。对于树，必然有且仅有一个点连出去的是狼边，①如果这条边指向其他连通分量，其他联通分量完全可以都是狼，那这个人就可能是个人，所以他不是铁狼。②如果指向自己的连通分量，如果他是狼，那么这个联通分量都是狼（因为都说了假话），如果他是人，那么从它指向的节点到它可能是狼可能是人，只有其他节点才是铁狼。所以用并查集判断连通分量，再往上搜索找出狼的个数就可以了。

另外，真的想吐槽HDU，自己手残将1e5写成105，结果它不给我判re，却判TLE

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
    int to;
    char ch;
}e[N];
vector<int> fa[N];
int f[N], n, ans;
int _find(int x){
    return f[x]==x?x:f[x]=_find(f[x]);
}
void conbine(int x, int y){
    int tx=_find(x), ty=_find(y);
    if(tx!=ty){
        f[tx]=f[ty];
    }
}
void count_ans(int x){
    ans++;
    for(int i=0; i<fa[x].size(); i++)
        count_ans(fa[x][i]);
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        ans=0;
        scanf("%d", &n);
        char s[100];
        for(int i=1; i<=n; i++)
            fa[i].clear();
        for(int i=1; i<=n; i++)
            f[i]=i;
        int v ;
        for(int i=1; i<=n; i++){
            scanf("%d %s", &v, s);
            e[i].to=v; e[i].ch=s[0];
            if(s[0]=='v'){
                conbine(i, v);
                fa[v].push_back(i);
            }
        }
        for(int i=1; i<=n; i++){
            int to=e[i].to;
            char ch=e[i].ch;
            if(ch=='w'){
                if( _find(i)==_find(to))
                    count_ans(to);
            }
        }
        printf("0 %d\n", ans);
    }
    return 0;
}