1.ignore
2.ignore
3.O(V2)

4.證明:
考慮一個頂點u,u屬于V
對BFS算法，當執行到u出隊時，有

for each v belongs to Adj[u]

            do if color[v] <- GRAY
                        d[v]<-   d[u]+1
                        n[v]<-    u
                        ENQUEUE(Q,v)（參考算導P325）
由此，對點u的鄰接鏈中的任意點v，如果v為白，則d[v]=d[u]+1。對u的鄰接鏈中任意一點均為如此，所以可知對v,v屬于u的鄰接點,d[v]=d[u]+1，即d[v]的值與順序無關

電腦畫圖太麻煩，不畫了，大概說下

對22-3圖b
S的兩個鄰接點，r&&w,若r在s鄰接表的前面，w在后面，則必然r為s的左兒子，w為右兒子。反之則反

5.don't understand

6. 二分圖...先跳過 DDD

7.沒想出來復雜度合適的算法，看了別人思路...

考慮BFS出廣度優先樹，然后DP求最大值.

if(x==leaf)
   D(x)=0;
else
   D(x)=max{ maxiD(x.childi)),maxij{(d(x).childi) + d(x).childj)} + 2}

8.