HDU 6370(思维)

淩亂°似流年 2022-05-17 11:06 170阅读 0赞

[传送门][Link 1]

思路：因为狼说什么都是可以的，所以全是狼是可以，村民为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;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6370