HDU多校Round 6

Solved:2

rank:452

I. Werewolf

没有铁人 找铁狼 如果一个环中只有一条狼人边那个人就是铁狼

说铁狼是好人的人也是铁狼

#include <bits/stdc++.h>
using namespace std;

int tmp, ans, lang;
char s[25];
struct node
{
    int to, nex, ty;
}E[200005];
int head[100005];
int col[100005];
int l[100005];
int r[100005];

void dfs(int x, int fa)
{
    col[x] = tmp;
    int c = head[x];
    for(int i = c; i; i = E[i].nex)
    {
        int v = E[i].to;
        if(v == fa) continue;
        if(col[v]) continue;
        dfs(v, x);
    }
}

void dfs1(int x, int fa)
{
    ans++;
    int c = head[x];
    for(int i = c; i; i = E[i].nex)
    {
        int v = E[i].to;
        if(v == fa) continue;
        if(E[i].ty) dfs1(v, x);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int cnt = 0;
        lang = tmp = ans = 0;
        int n; scanf("%d", &n);
        memset(head, 0, sizeof(int) * (n + 2));
        memset(col, 0, sizeof(int) * (n + 2));
        for(int i = 1; i <= n; i++)
        {
            int x; scanf("%d%s", &x, s);
            if(s[0] == 'v')
            {
                E[++cnt].to = x; E[cnt].nex = head[i]; E[cnt].ty = 0; head[i] = cnt;
                E[++cnt].to = i; E[cnt].nex = head[x]; E[cnt].ty = 1; head[x] = cnt;
            }
            else
            {
                lang++;
                l[lang] = i;
                r[lang] = x;
            }
        }

        for(int i = 1; i <= n; i++)
        {
            if(col[i]) continue;
            tmp++;
            dfs(i, 0);
        }

        for(int i = 1; i <= lang; i++)
            if(col[l[i]] == col[r[i]]) dfs1(r[i], 0);
        printf("0 %d
", ans);
    }
    return 0;
}