ACM 599 The Forrest for the Trees

用DFS就可以輕鬆AC


#include <stdio.h>
#include <stdbool.h>

// v[]紀錄某一點是否在測資中使用到，used[]紀錄某一點是否訪問過了
bool v[26], used[26], map[26][26], only_once;

void dfs(int node)
{
    int i;
   
    used[node] = true;
    for (i = 0; i < 26; i++)
        if (v[i] && (map[node][i] || map[i][node]) && !used[i])
        {
            dfs(i);
            only_once = false;
        }
}

int main(void)
{
    char ch;
    int i, j, t, tree, acorn;
   
    scanf("%d", &t);
    getchar();
   
    while (t--)
    {
        for (i = 0; i < 26; i++)
            v[i] = used[i] = false;
        for (i = 0; i < 26; i++)
            for (j = 0; j < 26; j++)
                map[i][j] = false;
       
        while (getchar() != '*')
        {
            scanf("%c,%c", &i, &j);
            getchar();
            getchar();
            i -= 'A';
            j -= 'A';
            map[i][j] = map[j][i] = true;
        }
        while (getchar() != '\n')
            continue;
        while ((ch = getchar()) != '\n')
            if (ch != ',')
                v[ch-'A'] = true;
       
        // 使用DFS搜尋
        tree = acorn = 0;
        for (i = 0; i < 26; i++)
            if (v[i] && !used[i])  // 檢查i點在測資有沒有用到、是否被訪問過了
            {
                only_once = true;
                dfs(i);
                if (!only_once)
                    tree++;
                else
                    acorn++;
            }
       
        printf("There are %d tree(s) and %d acorn(s).\n", tree, acorn);
    }

    return 0;
}