PAT A1021 Deepest Root

题目链接

我的解法

#include <cstdio>
#include <vector>
#include <algorithm>
/*
1、判断有没有多个块，有就直接输出
2、如果只有一条，就从每一个节点出发，开始时要先初始化，每个节点深度设置为1，然后vis设置为可访问！！！
*/
using namespace std;
const int maxn = 1e4 + 10;
int n;
struct Node {
    int v, depth, bestD;
    vector<int> child;
} G[maxn];
bool vis[maxn] = {false};

bool cmp(Node &a, Node &b) {
    if (a.bestD != b.bestD) return a.bestD > b.bestD;
    else return a.v < b.v;
}

void dfs(int st) {
    if(G[st].depth>G[st].bestD){
        G[st].bestD=G[st].depth;
    }
    vis[st] = true;
    for (int i = 0; i < G[st].child.size(); i++) {
        int next = G[st].child[i];
        if (vis[next] == false) {//只有下一个节点可以走的时候才能更新高度
            G[next].depth = G[st].depth + 1;
            dfs(next);
        }
    }
}
//判断连通分量
void dfs1(int st) {
    vis[st] = true;
    for (int i = 0; i < G[st].child.size(); i++) {
        int next = G[st].child[i];
        if (vis[next] == false) {
            dfs1(next);
        }
    }
}

int main() {
    scanf("%d", &n);
    int s, t;
    if (n==1) {
        printf("1");
        return 0;
    }
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &s, &t);
        G[s].child.push_back(t);
        G[t].child.push_back(s);
        G[s].v = s;
        G[t].v = t;
    }
    for (int i = 1; i <= n; i++) {
        G[i].depth = 1;
        G[i].bestD = -1;
    }
    //先看一下有没有多个块
    int com = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i] == false) {
            dfs1(i);
            com++;
        }
    }
    if (com > 1) {
        printf("Error: %d components", com);
    } else {//如果可以组成树
        for (int i = 1; i <= n; i++) {//从每一个节点，往下遍历
            fill(vis, vis + maxn, false);//先设置为没有遍历
            for (int j = 1; j <= n; j++) {
                G[j].depth = 1;
            }
            dfs(i);
        }
        sort(G + 1, G + n + 1, cmp);
        for (int i = 1; i <= n; i++) {
            if (G[i].bestD == G[1].bestD) {
                printf("%d\n", G[i].v);
            } else break;
        }
    }
    return 0;
}

算法笔记解法

1、使用并查集找出多个块。

2、使用vector记录每个最大的深度，如果更深，就更新最大深度，并清空vector！！