louisfghbvc的部落格

Description

圖上定義一個點的偏僻度(eccentricity)為他到最遠點的距離
中心點(central vertex)為偏僻度最小的點

Input

輸入第一行為一個數字T，代表測資的筆數。
接下來會有T筆測資，每一筆測資第一行有一個數字N
接下來有N-1行，第 i 行一個數字ai表示： i+1 與 ai 相連 (ai < i)

T < 100
0 < N <= 1000

Output

第一行一個數字為中心點個數
第二行輸出所有中心點

思路:

O(N), 2次dfs找樹的直徑，第1次從任意一點找葉子或根，第2次開始記錄離直徑點距離的陣列，接著中心=直徑/2, 直徑長度基數代表有2個中心，直徑長度偶數有1個中心。1條直徑上不可能有2個以上中心，在樹中這是一定的法則，比如 1 - 2 - 3 - 4。直徑長度=3(因為不整除2)，中心: 2, 3。至於樹的中心為啥等於半徑呢? 用反證法可以得到答案，這邊就不提了。

寫這題原因是因為itsa 71 第5題 想測試比較強的測資 看來沒問題呵呵

代碼:

#include <bits/stdc++.h>
#define N 1100
using namespace std;
vector<int> adj[N];
int dfn[N], mx, id;
bool vis[N];
void dfs(int u){
    vis[u] = true;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        if(vis[v]) continue;
        vis[v] = true;
        dfn[v] = dfn[u] + 1;
        if(dfn[v] > mx){
            mx = dfn[v];
            id = v;
        }
        dfs(v);
    }
}
int main()
{
    int t, n, x;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; ++i){
            adj[i].clear();
        }
        for(int i = 1; i < n; ++i){
            cin >> x;
            adj[x].push_back(i+1);
            adj[i+1].push_back(x);
        }
        memset(vis, 0, sizeof vis);
        mx = 0;
        dfn[1] = 0;
        dfs(1);

        memset(vis, 0, sizeof vis);
        dfn[id] = 0;
        dfs(id);

        int cnt = (mx & 1 ? 2 : 1), mid = mx / 2, mid2 = -1;
        cout << cnt << "\n";
        if(mx & 1)
            mid2 = mid + 1;
        bool f = true;
        for(int i = 1; i <= n && cnt > 0; ++i){ //找到cnt次數中心點結束迴圈
            if(dfn[i] == mid || dfn[i] == mid2){
                if(!f)
                    cout << " ";
                cout << i;
                cnt--;
                f = 0;
            }
        }
        cout << "\n";
    }
    return 0;
}