学步园

/*
最近看到一道谷歌笔试题，“已知一颗无向无环连通图T的所有顶点和边的信息，
现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要
求的树的根结点，并分析时空复杂度（描述算法即可，无需代码）”

其实就是给定一个无向连通图，求以哪些顶点为根可以得到深度最小的树，思路比较简单，
主要有两个步骤：
（1）首先选取1号结点作为树根，进行一遍DFS，在DFS时计算每个节点的countv值，表示
以当前节点作为树根的子树的最大深度+1
（2）进行第二遍DFS，进行DP，对于结点i的每个邻接点j，maxDepth(i, j)表示以i为根连同j表示的子树
    所构成的子树的最大深度，那么
        maxDepth(i, j) = countv[j],  当j尚未被访问
                         max(maxDepth(j, k)) + 1, k为j的邻居节点且k!=i, 当j被访问过
    上述公式画个图就很容易理解了，当j尚未被访问时期是就是使用了（1）中的计算结果，否则就是使用DP利用
    邻居的当前状态来计算自己的状态

  最后答案就是：min(max(maxDepth(i, j), for all i's neighbour j)), for all nodes i

  (1)的时间复杂度是O(V + E), (2) 的时间复杂度是O(V * E), 所以总体时间复杂度是O(V * E)
*/

#include <iostream><br /> #define MAX_N 100<br /> using namespace std;<br /> struct head //邻接表<br /> {<br /> int toId; //边的to结点的id<br /> int maxDepth; //表示以i为树根，连通j所带子树的最大深度<br /> head *next;<br /> head()<br /> {<br /> toId = maxDepth = 0;<br /> next = NULL;<br /> }<br /> }*heads[MAX_N];<br /> int countv[MAX_N]; //第一遍DFS时记录以当前节点作为子树的最大深度+1<br /> int res[MAX_N], num, minDepthVal; //记录最终结果，具有最小最大度数minDepthVal的结点个数num以及分别是哪些结点<br /> bool v[MAX_N]; //标记结点是否被访问了<br /> int nodeN; //结点个数<br /> //初始化<br /> void init()<br /> {<br /> for(int i = 0; i < MAX_N; i++)<br /> {<br /> countv[i] = res[i] = 0;<br /> v[i] = false;<br /> head *curPtr = heads[i];<br /> while(curPtr != NULL)<br /> {<br /> head *tempPtr = curPtr->next;<br /> delete curPtr;<br /> curPtr = tempPtr;<br /> }<br /> heads[i] = NULL;<br /> }<br /> }<br /> //向临街表中插入一条边<br /> void insertEdge(int from, int to)<br /> {<br /> head *newHead = new head();<br /> newHead->toId = to;<br /> newHead->next = heads[from];<br /> heads[from] = newHead;<br /> }<br /> //第一遍DFS计算Account<br /> int getAccount(int id)<br /> {<br /> //标记访问<br /> v[id] = true;<br /> //最大深度+1的初始值为1<br /> int maxD = 1;<br /> //遍历当前结点的临街表<br /> head *curPtr = heads[id];<br /> while(curPtr)<br /> {<br /> //邻接点id<br /> int toId = curPtr->toId;<br /> curPtr = curPtr->next;<br /> if(v[toId]) continue;<br /> int tempD = getAccount(toId);<br /> //更新最大深度+1的值<br /> if(tempD + 1 > maxD) maxD = tempD + 1;<br /> }<br /> //记录结果<br /> return countv[id] = maxD;<br /> }<br /> //第二遍DPF计算以每个结点为根得到的树的最大深度<br /> void getAnswer(int id)<br /> {<br /> //如果访问过就不再访问<br /> if(v[id]) return;<br /> //标记未访问结点为访问状态<br /> v[id] = true;<br /> head *curPtr = heads[id];<br /> //孤立点的最大深度是0，所以maxD的初始值为0<br /> int maxD = 0;<br /> //遍历邻接表<br /> while(curPtr)<br /> {<br /> //邻居结点的id<br /> int toId = curPtr->toId;<br /> //如果当前邻居点没有处理过，那么需要借助第一遍DFS时生成的countv数组计算以当前结点id以及它的邻居结点toId组成的子树的最大深度<br /> if(!v[toId])<br /> {<br /> //记录<br /> curPtr->maxDepth = countv[toId];<br /> if(countv[toId] > maxD) maxD = countv[toId];<br /> }<br /> //如果当前邻居点处理过了，那需要利用当前邻居结点toId的结果来得到id的状态值<br /> else<br /> {<br /> //遍历toId的所有邻居toIdd。toIdd构成的子树+toId+Id作为一棵新的子树<br /> int maxDD = 1;<br /> head *tempPtr = heads[toId];<br /> while(tempPtr)<br /> {<br /> int toIdd = tempPtr->toId;<br /> if(toIdd != id)<br /> {<br /> if(tempPtr->maxDepth + 1 > maxDD)<br /> maxDD = tempPtr->maxDepth + 1;<br /> }<br /> tempPtr = tempPtr->next;<br /> }<br /> curPtr->maxDepth = maxDD;<br /> if(maxDD > maxD) maxD = maxDD;<br /> }<br /> curPtr = curPtr->next;<br /> }<br /> //更新结果<br /> if(maxD < minDepthVal)<br /> {<br /> minDepthVal = maxD;<br /> num = 1;<br /> res[0] = id;<br /> }<br /> else if(maxD == minDepthVal)<br /> {<br /> res[num++] = id;<br /> }<br /> //DFS<br /> curPtr = heads[id];<br /> while(curPtr)<br /> {<br /> int toId = curPtr->toId;<br /> getAnswer(toId);<br /> curPtr = curPtr->next;<br /> }<br /> }<br /> int main()<br /> {<br /> int i, from, to;<br /> int root = 1;<br /> while(cin>>nodeN && nodeN != NULL)<br /> {<br /> init();<br /> for(i = 1; i < nodeN; i++)<br /> {<br /> cin>>from>>to;<br /> insertEdge(from, to);<br /> insertEdge(to, from);<br /> }<br /> getAccount(root);<br /> memset(v, 0, sizeof(v));<br /> num = 0; minDepthVal = INT_MAX;<br /> getAnswer(root);<br /> cout<<"Answer"<<endl;<br /> cout<<"depth "<<minDepthVal<<endl;<br /> cout<<"node ";<br /> for(i = 0; i < num; i++)<br /> cout<<res[i]<<" ";<br /> cout<<endl;<br /> }<br /> return 0;<br /> }