1

Graph Centroid is a vertex at equal distance or at distance less than or equal (N/2) where N is the size of the connected components connected through this vertex?! [Needs Correction?!]

Here's a problem at CodeForces that asks to find whether each vertex is a centroid, but after removing and replacing exactly one edge at a time.

Problem Statement

I need help to refine this PseudoCode / Algorithm.

Loop all Vertices:
 Loop all edges:
  Position each edge in every empty edge position between two unconnected nodes
  Count Size of each Connected Component (*1).
  If all sizes are less than or equal N/2,
   Then return true

The problem is that this algorithm will run in at least O(N*M^2)). It's not acceptable.

I looked up the answers, but I couldn't come up with the high level abstraction of the algorithm used by others. Could you please help me understand how these solutions work?

Solutions' Link

(*1) DFS Loop

4

2 回答 2

0

嗯，一棵树的质心可以在 O(N) 空间和时间复杂度中确定。

  1. 构造一个表示树的矩阵，行索引表示 N 个节点，第 i 行中的元素表示第 i 个节点连接到的节点。您也可以使用任何其他表示。

  2. 维护2个大小为N的线性数组，索引i分别代表第i个节点的深度（depth）和第i个节点的父节点（parent）。

  3. 还要维护另外 2 个线性数组，第一个包含树的 BFS 遍历序列（队列），另一个（leftOver）包含[N - 以该节点为根的子树中的节点数]的值。换句话说，第 i 个索引包含当第 i 个节点连同其所有子节点一起从树中删除时，整个树中剩余的节点数。

  4. 现在，以任意节点为根执行 BFS 遍历并填充数组“父”和“深度”。这需要 O(N) 时间复杂度。另外，在数组'queue'中记录遍历顺序。

  5. 从叶节点开始，将存在于以该节点为根的子树中的节点数与数组“leftOver”中父索引处的值相加。这也需要 O(N) 时间，因为您可以使用已经准备好的“队列”数组并从后面移动。

  6. 最后，遍历数组'leftOver'，将每个值修改为[N-1 - Initial Value]。'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 回答
0

我将尝试向您描述一种在线性时间内解决此问题的不太复杂的算法，以供将来参考，请参阅我的代码（它有一些评论）。

主要思想是您可以将树 T 植根于任意顶点并遍历它，对于每个顶点 V，您可以这样做：

  • 从 T 中切出子树 V。
  • 找到大小 <= N/2 的最重顶点 H（H 可以在任何 T 或子树 V 中）。
  • 移动子树 H 成为子树 V 的子树。
  • 用 V 重新根 T 并查找最重的顶点的大小是否 <= N/2

以前的算法可以仔细实现以获得线性时间复杂度，问题是它有很多情况要处理。

更好的办法是在顶点 C 处找到 T 和根 T 的质心 C。

将顶点 C 作为 T 的根很有用，因为它保证了 C 的每个后代的大小 <= N/2。

当遍历树时，我们可以避免检查树下最重的顶点，但是向上，每次我们访问一个子 W 时，如果我们在 W 处重新创建根 T，我们可以通过最重的大小（<= N/2）。

试着理解我解释的内容，如果有不清楚的地方请告诉我。

于 2016-09-05T15:15:05.180 回答