1021. Deepest Root 解析

DFS的改版 需要依次对每个顶点分别进行DFS然后求深度做大的几个顶点。

理清思路应该可以出来。

#include <iostream>#include <vector>#define Max 10010using namespace std;vector <int> g[Max];vector <bool> isVisit;vector <int> depth;vector <int> Root;int N;int ThisDepth = 1;int MaxDepth = 1;void DFS(int st ,int depth){ //st起点//	cout << "st： " << st << "d; " << depth << endl;	isVisit[st] = true;	ThisDepth = depth;	if (ThisDepth > MaxDepth)		MaxDepth = ThisDepth;	for (int i = 0; i < g[st].size(); i++) {		int v = g[st][i];		if (!isVisit[v]) {			 DFS(v, depth + 1);		}	}}int DFSTrave() {	int num = 0;//判断是否联通	int temp;	for (int j = 0; j < N ; j++) { //依次以各顶点为起点//		cout << " ----- " << j+1 << "-------" << endl;		ThisDepth = 1; MaxDepth = 1;		isVisit.clear();		isVisit.resize(N, false);		num = 1;		DFS(j, 1);		depth.push_back(MaxDepth);//保存深度		for (int i = 0; i < N ; i++) { //是否联通			if (!isVisit[i]) {				num++;				DFS(i, 1);			}		}		if (num != 1)			return num;	}	return num;}void FindMax() {	int max = 0;	for (int i = 0; i < depth.size(); i++) {//		cout << depth[i] << endl;		if (depth[i] > max) {			max = depth[i];			Root.clear();			Root.push_back(i);		}		else if (depth[i] == max) {			Root.push_back(i);		}	}}int main() {	int Head, Tail;	cin >> N;	for (int i = 0; i < N-1; i++) {//N-1 行		cin >> Head >> Tail;//		cout << Head << " " << Tail << endl;		Head--; Tail--;//归0		g[Head].push_back(Tail);		g[Tail].push_back(Head);	}#ifdef _DEBUG	for (int i = 0; i < N -1; i++) {		cout << "-----j: " << i+1 << "-------" << endl;		for (int j = 0; j < g[i].size(); j++) {			cout << g[i][j] +1 << endl;		}	}#endif	isVisit.resize(N, false);	int n = DFSTrave();	FindMax();#ifdef _DEBUG	cout << "depth" << endl;	for (int i = 0; i < depth.size(); i++) {		cout << depth[i] << endl;	}	cout << "----------" << endl;#endif		if (n != 1) {		cout << "Error: " << n << " components" << endl;	}	else {		for (int i = 0; i < Root.size(); i++) {			cout << Root[i]+1 << endl;		}	}		system("pause");	return 0;}