#include <iostream>
#include <queue>
#include <stack>
using namespace std;

const int MAXV = 20000;

typedef struct _linkGraph{
	int pos;
	_linkGraph *next;
}LinkGraph;

typedef struct {
	int parentIndex;
	int vCount;
	LinkGraph *adj;
	bool visited;
}GraphRow;

GraphRow Graph[MAXV+1];

void initGraph(int v)
{
	for(int i=1 ;i<=v ;i++){
		Graph[i].vCount=1;
		Graph[i].adj=NULL;
		Graph[i].visited=false;
		Graph[i].parentIndex = 0;
	}
}

inline void addGraph(int sPos ,int dPos)
{
	LinkGraph *nlg=new LinkGraph;
	nlg->pos=dPos;
	nlg->next=Graph[sPos].adj;
	Graph[sPos].adj = nlg ;
}

void clearGraph(int v)
{
	LinkGraph *clg ,*nlg;
	for(int i=1 ;i<=v ;i++){
		clg=Graph[i].adj;
		Graph[i].adj = NULL ;
		while(clg!=NULL){
			nlg=clg->next;
			delete clg;
			clg=nlg;
		}
	}
}

void buildGraph(int v ,int e)
{
	int sPos ,dPos;
	for(int i=0 ;i<e ;i++){
		scanf("%d %d" ,&sPos ,&dPos);
		addGraph(sPos ,dPos);
		addGraph(dPos ,sPos);
	}
}
//bfs recursion,this would tle!!!
int trackVCount(int root)
{
	int count=1;
	LinkGraph *adj=Graph[root].adj;
	Graph[root].visited=true;
	while(adj!=NULL){
		if(false == Graph[adj->pos].visited){
			count += trackVCount(adj->pos);
		}
		adj=adj->next;
	}
	Graph[root].vCount=count;
	return count;
}
//dfs ,non-recursion!!
int dfsCount(int v ,int root)
{
	LinkGraph *adj=NULL;
	stack<int> nodes;


	int curNodeIndex;

	nodes.push(root) ;
	while(!nodes.empty()){
		curNodeIndex = nodes.top();
		if(true == Graph[curNodeIndex].visited){
			Graph[Graph[curNodeIndex].parentIndex].vCount += Graph[curNodeIndex].vCount;
			//printf("node  ,count : %d %d\n" ,curNodeIndex ,Graph[curNodeIndex].vCount) ;
			nodes.pop();
			continue ;
		}//else

		adj=Graph[curNodeIndex].adj ;
		while(adj !=NULL){
			if(false == Graph[adj->pos].visited ){
				nodes.push(adj->pos);
				Graph[adj->pos].parentIndex = curNodeIndex ;
			}
			adj = adj->next ;
		}
		Graph[curNodeIndex].visited = true ;
	}
	return 1;	
}

void printNodes(int v)
{
	int minResult=v;
	int minResultPos=-1;
	LinkGraph *adj;
	int aliVCount;
	bool isNodeOk;
	int curMaxNodes;
	for(int i=1 ;i<=v ;i++){
		if(v-Graph[i].vCount >= minResult)
			continue;
		isNodeOk=true;
		adj=Graph[i].adj;
		curMaxNodes=v-Graph[i].vCount;
		while(adj != NULL){
			aliVCount=Graph[adj->pos].vCount;
			//only consider child  node!!
			if(aliVCount < Graph[i].vCount){
				if(aliVCount >= minResult){
					isNodeOk=false;
					break;
				}else if(aliVCount > curMaxNodes)
					curMaxNodes=aliVCount;
			}
			adj=adj->next;
		}
		if(true == isNodeOk){
			minResult=curMaxNodes;
			minResultPos=i;
		//	printf("%d %d\n" ,i ,curMaxNodes);
		}
	}
	printf("%d %d\n" ,minResultPos ,minResult);
}

int main()
{
	int testcase;
	int v;
	freopen("1655.txt" ,"r" ,stdin);
	scanf("%d" ,&testcase);
	while(testcase-- > 0){
		scanf("%d" ,&v);
		initGraph(v);
		buildGraph(v ,v-1);
		dfsCount(v ,1) ;
	//	trackVCount(1);
		printNodes(v);

		clearGraph(v);
	}
	return 0;
}

• Re:这题真变态 ，非递归 DFS 的 O(V) 算法也超时！大牛帮瞧瞧！！ (72) windyrobin 2008-08-07 09:46:17