1

グラフ重心は、等距離またはそれ以下の距離 (N/2) にある頂点です。ここで、N はこの頂点を介して接続された接続コンポーネントのサイズです?! 【要修正?!】

各頂点が重心であるかどうかを確認するように求める CodeForces の問題がありますが、一度に 1 つのエッジを正確に削除および置換した後です。

問題文

この PseudoCode / Algorithm を改良するために助けが必要です。

すべての頂点をループする:
 すべてのエッジをループします。
  接続されていない 2 つのノード間のすべての空のエッジ位置に各エッジを配置します
  各 Connected Component のカウント サイズ (*1)。
  すべてのサイズが N/2 以下の場合、
   その後、trueを返します

問題は、このアルゴリズムが少なくとも O(N*M^2)) で実行されることです。受け入れられません。

答えを調べましたが、他の人が使用しているアルゴリズムの高レベルの抽象化を思い付くことができませんでした。これらのソリューションがどのように機能するかを理解するのを手伝ってもらえますか?

ソリューションのリンク

(*1) DFSループ

4

2 に答える 2

0

この問題を線形時間で解決するためのそれほど複雑ではないアルゴリズムについて説明します。今後の参考のために、私のコードを参照してください(コメントがいくつかあります)。

主なアイデアは、ツリー T を任意の頂点でルートし、それをトラバースできるということです。頂点 V ごとに、これを行うことができます。

  • T から部分木 V を切り取ります。
  • サイズが N/2 以下の最も重い頂点 H を見つけます (H は T またはサブツリー V のいずれかにある可能性があります)。
  • 部分木 H を移動して、部分木 V の子にします。
  • T を V で再ルートし、最も重い頂点のサイズが N/2 以下かどうかを調べます

以前のアルゴリズムは、線形時間の複雑さを得るために慎重に実装できますが、問題は、処理するケースが多いことです。

より良いアイデアは、T の重心 C と頂点 C でのルート T を見つけることです。

頂点 C を T のルートとして持つことは、C のすべての子孫のサイズが N/2 以下であることを保証するので便利です。

ツリーをトラバースするとき、ツリーの下にあるが上にある最も重い頂点をチェックすることを避けることができます。子 W にアクセスするたびに、T を W にルートすると、最も重いサイズ (<= N/2) を渡すことができます。

私が説明したことを理解するようにしてください。不明な点があればお知らせください。

于 2016-09-05T15:15:05.180 に答える
0

さて、木の重心は O(N) 空間と時間の複雑さで決定できます。

  1. ツリーを表す Matrix を構築します。行インデックスは N ノードを表し、i 番目の行の要素は i 番目のノードが接続されているノードを表します。他の表現もできます。

  2. サイズ N の 2 つの線形配列を維持します。インデックス i は、それぞれ i 番目のノードの深さ (深さ) と i 番目のノードの親 (親) を表します。

  3. また、さらに 2 つの線形配列を維持します。最初の配列にはツリー (キュー) の BFS トラバーサル シーケンスが含まれ、もう 1 つの配列 (leftOver) には[N - そのノードをルートとするサブツリー内のノード数]の値が含まれます。つまり、i 番目のインデックスには、i 番目のノードがそのすべての子と共にツリーから削除されたときに、ツリー全体に残るノードの数が含まれます。

  4. ここで、任意のノードをルートとして BFS トラバーサルを実行し、配列「親」と「深さ」を埋めます。これには O(N) 時間の複雑さがかかります。また、走査シーケンスを配列「queue」に記録します。

  5. リーフ ノードから開始して、そのノードをルートとするサブツリーに存在するノードの数を、配列 'leftOver' の親インデックスの値と共に追加します。すでに準備された「キュー」配列を使用して後方から移動できるため、これには O(N) 時間もかかります。

  6. 最後に、配列「leftOver」をトラバースし、各値を [N-1 - 初期値] に変更します。「leftOver」配列が用意されています。コスト: 別の O(N)。

  7. あなたの仕事はほとんど終わりました。次に、この「leftOver」配列を繰り返し処理し、値が floor(N/2) に最も近いインデックスを見つけます。ただし、この値が floor(N/2) を超えてはなりません。

このインデックスは、ツリーのセントロイドのインデックスです。全体的な時間の複雑さ: O(N)。

Java コード:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

class Find_Centroid
{
    static final int MAXN=100_005;
    static ArrayList<Integer>[] graph;
    static int[] depth,parent;  // Step 2
    static int N;

    static Scanner io=new Scanner(System.in);

    public static void main(String[] args)
    {
        int i;
        N=io.nextInt();
                    // Number of nodes in the Tree
        graph=new ArrayList[N];

        for(i=0;i<graph.length;++i)
            graph[i]=new ArrayList<>();
                    //Initialisation

        for(i=1;i<N;++i)
        {
            int a=io.nextInt()-1,b=io.nextInt()-1;
                    // Assuming 1-based indexing
            graph[a].add(b);    graph[b].add(a);
                    // Step 1
        }
        int centroid = findCentroid(new java.util.Random().nextInt(N));
                    // Arbitrary indeed... ;)

        System.out.println("Centroid: "+(centroid+1));
                    // '+1' for output in 1-based index
    }

    static int[] queue=new int[MAXN],leftOver;
                    // Step 3

    static int findCentroid(int r)
    {
        leftOver=new int[N];
        int i,target=N/2,ach=-1;

        bfs(r);     // Step 4
        for(i=N-1;i>=0;--i)
            if(queue[i]!=r)
                leftOver[parent[queue[i]]] += leftOver[queue[i]] +1;
                    // Step 5
        for(i=0;i<N;++i)
            leftOver[i] = N-1 -leftOver[i];
                    // Step 6
        for(i=0;i<N;++i)
            if(leftOver[i]<=target && leftOver[i]>ach)
                    // Closest to target(=N/2) but does not exceed it.
            {
                r=i;    ach=leftOver[i];
            }
                    // Step 7
        return r;
    }
    static void bfs(int root)   // Iterative
    {
        parent=new int[N];  depth=new int[N];
        int st=0,end=0;
        parent[root]=-1;    depth[root]=1;
                // Parent of root is obviously undefined. Hence -1.
                // Assuming depth of root = 1
        queue[end++]=root;
        while(st<end)
        {
            int node = queue[st++], h = depth[node]+1;
            Iterator<Integer> itr=graph[node].iterator();
            while(itr.hasNext())
            {
                int ch=itr.next();
                if(depth[ch]>0)     // 'ch' is parent of 'node'
                    continue;
                depth[ch]=h;   parent[ch]=node;
                queue[end++]=ch;    // Recording the Traversal sequence
            }
        }
    }
}

ここで、問題http://codeforces.com/contest/709/problem/Eについて、各ノード i を反復し、それをルートと見なし、>N/2 ノードを持つ子を下降し続け、到達を試みますその下に N/2 未満のノード (N/2 ノードに最も近い) を持つノードで。このノードをそのすべての子とともに削除すると、'i' がセントロイドになる場合は、'1' を出力し、それ以外の場合は 0 を出力します。'leftOver' 配列が既に存在するため、このプロセスは効率的に実行できます。

実際には、妨害ノード (i が重心になるのを妨げているノード) をその子と共に切り離し、それを i 番目のノード自体にアタッチしています。サブツリーには最大で N/2 個のノードがあることが保証されているため (前に確認したように)、問題は発生しません。

ハッピーコーディング..... :)

于 2018-01-24T16:26:01.743 に答える