PAT_甲级_1021 Deepest Root

题目大意:

给出N个节点和N-1条边,问它们是否可以形成一颗树,如果能选择输的深度最大的根节点,输出所有满足该条件的根节点,如果不是一颗树输出Error: K components,其中K是连通分量的个数.

算法思路:

首先注意到,该题的图有不连通,所以必须得先判断当前图是否连通,具体做法就是使用$DFS$常规遍历一遍该图,获得连通分量的个数connected_component_count,如果不为1,直接输出结果即可,否则就得遍历每一个节点作为根节点的生成树,并且得记录每一个生成树的最大高度,这里使用max_depth数组保存,获取最大高度的方法也比较直观,直接在$DFS$遍历的时候访问当前节点,就更新最大高度。这里还使用了$maxDepth$保存全局最大深度,最后只需遍历max_depth数组,依次输出和$maxDepth$相等的节点的编号即可。

注意点:

  • 1、如果使用邻接矩阵,测试点三出现超时现象。
  • 2、每次选取一个结点进行深度优先遍历的时候,得初始化$visited$数组

提交结果:

PAT_甲级_1021 Deepest Root_第1张图片

AC代码:

#include 
#include 
#include 
#include 

using namespace std;

vector G[10005];// 邻接表
bool visited[10005] = {};//访问标记数组
int max_depth[10005];//每一个节点的最大深度
int N;// 顶点数目

void DFS(int start,int depth,int &maxDepth){
    // 访问当前顶点
    visited[start] = true;
    maxDepth = max(maxDepth,depth);
    for (int i : G[start]) {
        if(!visited[i]){
            // 访问所有与start连通,没有被攻占,并且没有被访问的节点
            DFS(i,depth+1,maxDepth);
        }
    }
}

int DFSTraverse(){
    int connected_component_count = 0;
    for (int i = 1; i <= N; ++i) {
        if(!visited[i]){
            int maxDepth = 0;// 无实际意义,传递参数需要
            DFS(i,0,maxDepth);
            ++connected_component_count;
        }
    }
    return connected_component_count;
}

int main()
{
    scanf("%d",&N);
    int a,b;
    for (int i = 0; i < N - 1; ++i) {
        scanf("%d %d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    // 连通分量个数
    int connected_component_count = DFSTraverse();
    if(connected_component_count!=1){
        printf("Error: %d components",connected_component_count);
    } else {
        // 从每一个顶点开始遍历整个图
        int maxDepth = 0;// 所有节点的生成树的最大深度
        for (int i = 1; i <= N; ++i) {
            int depth = 0;// 当前节点生成树的最大深度
            memset(visited,0,sizeof(visited));
            DFS(i,1,depth);
            maxDepth = max(maxDepth,depth);// 保存全局最大深度
            max_depth[i] = depth;// 统计每一个节点的最大深度
        }
        for (int j = 1; j <= N; ++j) {
            if(max_depth[j]==maxDepth){
                printf("%d\n",j);
            }
        }
    }
    return 0;
}

你可能感兴趣的