# 資料結構題 - 血緣關係 - APCS - by Peter Wang
## 題目資訊
此題為2016.3.5 測驗中的題目4
###### tags: `APCS` `Tree` `DFS`

## Rooted Tree定義

在一棵 *n* 個節點的有根樹中,每個節點都是以 *1~n* 的不同數字來編號,描述一棵有根樹必須定義節點與節點之間的親子關係。一棵有根樹恰有一個節點沒有父節點(parent),此節點被稱為根節點(root),除了根節點以外的每一個節點都恰有一個父節點,而每個節點被稱為是它父節點的子節點(child),有些節點沒有子節點,這些節點稱為葉節點(leaf)。在當有根樹只有一個節點時,這個節點既是根節點同時也是葉節點。在圖形表示上,我們將父節點畫在子節點之上,中間畫一條邊(edge)連結。例如：下圖中表示的是一棵 9 個節點的有根樹,其中,節點 1 為節點 6 的父節點,而節點 6 為點 1 的子節點;又 5 、 3 與 8 都是 2 的子節點。節點 4 有父節點,所以節點 4 是根節點;而 6 、 9 、 3 與 8 都是葉節點。
## Unrooted Tree定義
無根樹是一個連接的無向圖，沒有循環。具有一個鄰居的節點是樹的葉子，其餘的頂點是樹的內部節點。相較於 Rooted Tree 樹中的任一節點都沒有父節點，其邊也沒有特定方向。

## DFS概述
用來遍歷樹(tree)或圖(graph)的演算法。
由圖的某一點開始搜尋，先探尋鄰接邊(edge)上未搜尋的一點，並儘可能往深處搜索，直到最後，再回溯(backtracking)到前一個節點，持續拜訪未搜尋的節點，直到到達目標節點或已經遍歷所有節點。
如下圖由 4 開始走訪按照數字順序依序 DFS ，這也是基本 DFS 圖像化的概念。
當然 DFS 還有分成不同種走訪方式這裡就先不多做解釋。
## 題目敘述
下圖為範例關係圖。
假設 0 是 7 的孩子， 1、2 和 3 是 0 的孩子， 4 和 5 是 1 的孩子， 6 是 3 的孩子。我們可以輕易的發現最遠的親戚關係為 4 ( 或 5) 和 6 ，他們的"血緣距離"是 4 (4→1→0→3→6)。
給予關係圖，請找出最遠的"血緣距離"。

### 輸入：
每筆側資中，
第一行為一個正整數 *N* 代表成員的個數，每人以 *0~N-1* 之間唯一的編號代表。
接著的 *N-1* 行，每行有兩個以一個空白隔開的整數 *a* 與 *b* (0 ≤ *a*, *b* ≤ *N-1*)，代表 *b* 是 *a* 的孩子。

### 輸出：
每筆測資輸出一行，輸出最遠"血緣距離"的答案。

## 解題思路
此樹為無向圖 (圖1)。
不管以哪點當root，都能成為一棵樹 (圖2、圖3)。
(圖3) 從節點 0 (當root)開始做 DFS ，計算每個節點與節點 0 的距離 。(不管從哪個節點開始，最後答案都會一樣。)
選一個與(圖3)中節點 0 距離最遠的節點當成新的root (圖4中的節點 4 )，再做一次DFS，計算每個節點與節點 4的距離。並輸出最大距離。
[圖源](https://yuihuang.com/zj-b967/)https://yuihuang.com/zj-b967/

## 程式碼

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
vector <ll> tree[100004];
ll h[100004];
ll N = 0;
void dfs(ll node,ll par){
  for (auto i:tree[node]){
        if (i != par){
            h[i] = h[node]+1;
            dfs(i, node);
        }
    }
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  while(cin>>n){
    for(int i=0;i<n;i++){
      tree[i].clear();
    }
    fill(h,h+n+1,0);
    for(ll i=1;i<=n-1;i++){
      ll a,b;
      cin>>a>>b;
      tree[a].push_back(b);
      tree[b].push_back(a);
    }
    dfs(0,-1);
    int maxnode=-1;
    for(int i=0;i<=n-1;i++){
      if(h[i]>maxnode){
        maxnode=h[i];
        N=i;
      }
    }
    fill(h,h+n+1,0);
    dfs(N,-1);
    maxnode=-1;
    for(int i=0;i<n;i++){
      if(h[i]>maxnode){
        maxnode=h[i];
      }
    }
    cout<<maxnode<<endl;
  } 
}

## 資料來源
[Zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=b967)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 9:59 AM]