ARC037B - バウムテスト

atcoder.jp

頂点の数 N は 100 以下なので、深さ優先探索を行った場合の深さは最大でもたかだか 100。今回は趣向を変えて、再帰で深さ優先探索を実装してみた。スタック使うよりすんなり書けたので、今後も使えそうな問題があれば使っていきたい。

using System;
using System.Collections.Generic;

namespace ARC037B
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var M = int.Parse(input[1]);
            var visited = new HashSet<int>();
            var relations = new Dictionary<int, List<int>>();
            for (var i = 0; i < M; i++)
            {
                input = Console.ReadLine().Split(' ');
                var u = int.Parse(input[0]);
                var v = int.Parse(input[1]);
                if (!relations.ContainsKey(u))
                {
                    relations[u] = new List<int>();
                }
                relations[u].Add(v);
                if (!relations.ContainsKey(v))
                {
                    relations[v] = new List<int>();
                }
                relations[v].Add(u);
            }

            var answer = 0;
            for (var i = 1; i <= N; i++)
            {
                if (IsTree(-1, i, relations, visited))
                {
                    answer++;
                }
            }
            Console.WriteLine(answer);
        }

        static bool IsTree(int prev, int current, Dictionary<int, List<int>> relations, HashSet<int> visited)
        {
            // 訪れたことのある点だったら閉路がある
            if (visited.Contains(current))
            {
                return false;
            }
            visited.Add(current);

            // 辺が無い場合は末端なので、現在の点より先は無い
            if (!relations.ContainsKey(current))
            {
                return true;
            }

            foreach (var next in relations[current])
            {
                // prev は既に訪れているのでスキップ
                if (next != prev && !IsTree(current, next, relations, visited))
                {
                    return false;
                }
            }

            // ここまでくれば、この部分木に閉路は無い
            return true;
        }
    }
}