32

コード チャレンジで行き詰まっています。ヒントが欲しいです。

問題: ツリー データ構造 (サイクルなし) が与えられ、ノードの数が偶数の小さなツリーを作成して、できるだけ多くの「エッジ」(接続) を削除するよう求められます。ノードと接続の数が偶数であるため、この問題は常に解決可能です。

あなたの仕事は、削除されたエッジを数えることです。

入力: 入力の最初の行には、2 つの整数 N と M が含まれます。N は頂点の数で、M はエッジの数です。2 <= N <= 100. 次の M 行には、ツリーのエッジを指定する 2 つの整数 ui と vi が含まれます。(1 ベースのインデックス)

出力: 削除されたエッジの数を出力します。

サンプル入力

10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8

サンプル出力: 2

説明 : エッジ (1, 3) と (1, 6) を削除すると、目的の結果が得られます。

4

8 に答える 8

23

BFSを使用してノードを移動しました。まず、配列を個別に維持して、子ノードの総数+1を格納します。したがって、最初に、この配列の値1を持つすべてのリーフノードを割り当てることができます。ここで、最後のノードから開始して、各ノードの子の数を数えます。これは下から上に機能し、子ノードの数を格納する配列は、実行時にコードを最適化するのに役立ちます。

すべてのノードの子ノードの数を取得した後で配列を取得したら、偶数のノードを持つノードを数えるだけで答えが得られます。注：最終ステップのカウントにルートノードを含めませんでした。

于 2012-08-31T16:49:38.523 に答える
6

これが私の解決策です。私は bfs ツリーを使用せず、各ノードとその子ノードの総数を保持するために別の配列を割り当てただけです。

import java.util.Scanner;
import java.util.Arrays;

public class Solution {
        public static void main(String[] args) {
                int tree[];
                int count[];

                Scanner scan = new Scanner(System.in);

                int N = scan.nextInt(); //points
                int M = scan.nextInt();

                tree = new int[N];
                count = new int[N];
                Arrays.fill(count, 1);

                for(int i=0;i<M;i++)
                {
                        int u1 = scan.nextInt();
                    int v1 = scan.nextInt();

                    tree[u1-1] = v1;

                    count[v1-1] += count[u1-1];

                    int root = tree[v1-1];

                    while(root!=0)
                    {
                        count[root-1] += count[u1-1];
                        root = tree[root-1];
                    }
                }

                System.out.println("");

                int counter = -1;
                for(int i=0;i<count.length;i++)
                {
                        if(count[i]%2==0)
                        {
                                counter++;
                        }

                }
                System.out.println(counter);

        }

}
于 2012-10-26T00:50:50.317 に答える
2

入力を観察すると、各ノードの下にあるノードの数を数えるのは非常に簡単であることがわかります。(ab) をエッジ入力と見なします。すべての場合で、a が子で、b が直接の親です。入力には、常にボトムアップで表されるエッジがあります。

したがって、本質的には偶数カウントを持つノードの数です (ルート ノードを除く)。以下のコードを Hackerrank に提出し、すべてのテストに合格しました。入力のすべてのケースがルールを満たしていると思います。

def find_edges(count):
    root = max(count)

    count_even = 0

    for cnt in count:
        if cnt % 2 == 0:
            count_even += 1

    if root % 2 == 0:
        count_even -= 1

    return count_even

def count_nodes(edge_list, n, m):
    count = [1 for i in range(0, n)]

    for i in range(m-1,-1,-1):
        count[edge_list[i][1]-1] += count[edge_list[i][0]-1]

return find_edges(count)
于 2013-08-06T21:40:21.827 に答える
1

私の最初の傾向は、単一頂点のサブツリーを残すようにエッジをカットできないため、リーフ ノードから作業することです。

于 2012-08-20T18:53:29.047 に答える
1

すべてのテスト ケースに合格するために使用したアプローチを次に示します。

  1. 頂点 1 をルートとしてマーク
  2. 現在のルート頂点から始めて、各子を検討します。子とそのすべての子の合計が偶数の場合、そのエッジをカットできます
  3. 次の頂点 (ルート頂点の子) に降りて、それを新しいルート頂点とします。すべてのノードをトラバースするまで、手順 2 を繰り返します (深さ優先検索)。
于 2015-11-22T04:32:28.190 に答える
0

解決策 - すべてのエッジをトラバースし、偶数エッジの数を数えます

ツリーからエッジを削除した結果、頂点の数が偶数の 2 つのツリーになった場合、そのエッジを偶数エッジと呼びましょう。

ツリーからエッジを削除した結果、頂点の数が奇数の 2 つのツリーができた場合、そのエッジを奇数エッジと呼びましょう。

これがRubyでの私のソリューションです

num_vertices, num_edges = gets.chomp.split(' ').map { |e| e.to_i }
graph = Graph.new
(1..num_vertices).to_a.each do |vertex|
  graph.add_node_by_val(vertex)
end

num_edges.times do |edge|
  first, second = gets.chomp.split(' ').map { |e| e.to_i }
  graph.add_edge_by_val(first, second, 0, false)
end

even_edges = 0
graph.edges.each do |edge|
  dup = graph.deep_dup
  first_tree = nil
  second_tree = nil
  subject_edge = nil
  dup.edges.each do |e|
    if e.first.value == edge.first.value && e.second.value == edge.second.value
      subject_edge = e
      first_tree = e.first
      second_tree = e.second
    end
  end
  dup.remove_edge(subject_edge)
  if first_tree.size.even? && second_tree.size.even?
    even_edges += 1
  end
end
puts even_edges

注 -ここをクリックして、Graph、Node、および Edge クラスのコードを確認してください。

于 2015-10-19T03:13:01.573 に答える