Centroid of Tree

Centroid of Tree

centroid란 트리에서 어떤 노드(와 연결된 엣지들)를 삭제했을 때, 분리된 component의 크기가 n/2 이하가 되는 노드를 말한다. centroid는 트리에서 반드시 최소 하나는 존재하며, 최대 2개를 가질 수도 있다.

centroid를 찾는 방법은 두 번의 dfs를 돌려보면 된다.
첫 번째 dfs(subtreeDFS) 에서는 어떤 임의의 노드 x를 트리의 루트라고 가정하고 dfs를 시작한다. x 노드의 subtree가 갖고 있는 노드의 개수를 subtree[] 배열에다가 저장해놓는다.
두 번째 dfs(findCentroid) 에서는 구해놓은 subtree[]값을 통해 현재 노드 i를 삭제했을 경우, 그로 인해 분할되는 component들(subtree)의 값이 모두 n/2이하라면 centroid 이다.

#include<stdio.h>
#include<vector>
using namespace std;
const int SIZE = 10009;

vector<int> tree[SIZE],centroid;
int subtree[SIZE];
int n;

int subtreeDFS(int node,int p){
    subtree[node] = 1;
    for(int next : tree[node]){
        if(next == p) continue;
        subtree[node] += subtreeDFS(next,node);
    }
    return subtree[node];
}

void findCentroid(int node,int p){
    bool isCentroid = true;
    for(int next : tree[node]){
        if(next == p) continue;
        if(subtree[next] > n/2) {
            isCentroid = false;
        }
        findCentroid(next,node);
    }
    if(n - subtree[node] > n/2) isCentroid = false;
    if(isCentroid) centroid.push_back(node);
}

int main(){
    scanf("%d",&n);
    for(int i=0 ; i<n-1 ; i++){
        int a,b;    scanf("%d %d",&a,&b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    subtreeDFS(1,-1);
    for(int i=1 ; i<=n ; i++){
        printf("%d ",subtree[i]);
    }
    printf("\n");
    findCentroid(1,-1);

    for(int x : centroid) printf("%d ",x);
}

아래처럼 subtree를 구하는 과정에서 몇개의 조건만 추가해주면 dfs한번으로 구할 수도 있다.

#include<stdio.h>
#include<vector>
using namespace std;
const int SIZE = 10009;

vector<int> tree[SIZE],centroid;
int subtree[SIZE];
int n;

void subtreeDFS(int node,int p){
    subtree[node] = 1;
    bool isCentroid = true;
    for(int next : tree[node]){
        if(next == p) continue;
        subtreeDFS(next,node);
        subtree[node] += subtree[next];
        if(subtree[next] > n/2) isCentroid = false;
    }
    if(n - subtree[node] > n/2) isCentroid = false;
    if(isCentroid) centroid.push_back(node);
}

int main(){
    scanf("%d",&n);
    for(int i=0 ; i<n-1 ; i++){
        int a,b;    scanf("%d %d",&a,&b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    subtreeDFS(1,-1);
    for(int i=1 ; i<=n ; i++){
        printf("%d ",subtree[i]);
    }
    printf("\n");

    for(int x : centroid) printf("%d ",x);
}