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.