1021 Deepest Root (2)

找一个连通图的“最深根节点”

求一棵树中所有路径最长的节点对

(阿弥陀佛,昨天困困今天还是困困。明天过小年狗逼老师还要答辩,差不多得了😅

承接上篇博客,来说一说标答对于第二个问题的精巧做法。

(此处省略题面)

标答的思路

(原题可等价于“寻找一棵树中最长路径的集合”。)

首先,从树上的任何一个节点出发,用dijkstra算法计算出离该节点距离最远的节点集合A;
其次,从节点集合A中的任何一个节点出发,用dijkstra算法计算出离这个节点距离最远的节点集合B;
最后,求A和B的并集即是“能使树的深度最深”的根节点集合。

(只需要进行两次dijkstra,比起n次dijkstra,性能方面更加优越)

思路证明

证明一:树上如果有多条最长路径,所有最长路径一定有一段公共重合区间或者交于一个公共点。

先证明每两条最长路径必然有公共点:

假设存在两条最长路径不相交,如下图\(\overline{XY}\)和\(\overline{WZ}\)所示,假设在\(\overline{XY}\)上任意一节点 P,在\(\overline{WZ}\)上任意一节点 Q,由于树的连通性, P, Q 之间必然存在一条路径使之连通,又因为\(\overline{XY}\)和\(\overline{WZ}\)不相交,则\(\overline{PQ}\)上必然存在 不同的两点 R, S ,使得 R, S 之间的点既不在\(\overline{XY}\)上,也不在\(\overline{WZ}\)上,则可以通过与\(\overline{RS}\)拼接得到比\(\overline{XY}\)更长的路径(例如下图中的\(\overline{XRSZ}\)),这与原假设“\(\overline{XY}\)是最长的路径”相矛盾。因此每两条最长路径必然有公共点

再证明所有最长路径必然有共同的公共点:

由于每两条最长路径都有交点,假设 最长路径\(\overline{X_{1}Y_{1}}\) 、 \(\overline{X_{2}Y_{2}}\) 和 \(\overline{X_{3}Y_{3}}\) 交于不同的三点Z1、Z2和Z3,则这三点形成了一个环,这与原条件“树”相矛盾。因此所有最长路径必然有共同的公共点

证明二:从任意节点出发进行遍历,得到的最深节点一定是所求根节点集合的一部分。

如下图,假设从任意节点R出发得到的最长路径是\(\overline{RQ}\),

如果\(\overline{RQ}\)与\(\overline{WZ}\)无公共点,由于树的连通性,从R出发一定有一条到W的路径\(\overline{WOR}\)

易知\(\overline{ROW}\leq\overline{RQ}\),则\(\overline{ZORQ}\gt\overline{WZ}\),矛盾!因此\(\overline{RQ}\)与\(\overline{WZ}\)必然存在公共点

假设公共点为O,如下图示,则易知 \(\overline{ROZ}\leq\overline{ROQ}\) ,即 \(\overline{OZ}\leq\overline{OQ}\) ,则\(\overline{WZ}\leq\overline{WOQ}\) ,由于 \(\overline{WZ}\) 是最长路径,所以 \(\overline{WOQ}\) 也是最长路径,也就是说从R开始遍历所找到的每一个最深节点一定是一条最长路径的一个端点,即“最深根节点”之一。

证明三:两次遍历结果的并集恰好为所求的节点集合。

如下图,假设所有最长路径的公共区间为 \(\overline{C_{1}C_{2}}\) (C1可以与C2重合)

若R是第一次找到的点集中的一点,则说明R所在的子树是所有子树中最深的子树之一,且R的深度为当前子树最深,那么第二次遍历则会找到除了R所在的子树以外所有最深的子树中最深点的集合,如此显然就找到了所有的最长路径,由于最长路径的两端都是符合题目条件的根节点,所以两次结果的并集就为所求的节点集合。

使用优先队列来做集合的去重。。。(不会用set)
(关于优先队列的顺序:

priority_queue<int, vector<int>, less<int> > q;//默认,从大到小排
//greater<int> 从小到大排

代码如下:

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN 10001
#define INFI 10000001
using namespace std;
vector<int> map[MAXN];
priority_queue<int, vector<int>, greater<int>> q;
int n;
void dijkstra(int c)
{
    int dis[MAXN];
    bool vis[MAXN];
    vector<int> v;

    fill(vis + 1, vis + n + 1, 0);
    fill(dis, dis + n + 1, INFI);

    for (int i = 0; i < map[c].size(); i++)
    {
        dis[map[c][i]] = 1;
    }
    dis[c] = 0;
    vis[c] = true;

    for (int i = 1; i <= n; i++)
    {
        int min = INFI;
        int mini = 0;
        for (int j = 1; j <= n; j++)
        {
            if (vis[j])
            {
                continue;
            }
            else if (dis[j] < min)
            {
                min = dis[j];
                mini = j;
            }
        }
        vis[mini] = true;
        for (int j = 0; j < map[mini].size(); j++)
        {
            if (vis[map[mini][j]])
            {
                continue;
            }
            else
            {
                if (dis[map[mini][j]] > dis[mini] + 1)
                {
                    dis[map[mini][j]] = dis[mini] + 1;
                }
            }
        }
    }
    int max = -1;
    for (int i = 1; i <= n; i++)
    {
        if (max < dis[i])
        {
            max = dis[i];
            v.clear();
            v.push_back(i);
        }
        else if (max == dis[i])
        {
            v.push_back(i);
        }
    }
    for (int i = 0; i < v.size(); i++)
    {
        q.push(v[i]);
    }
}

int count() // DFS,并查集也可
{
    stack<int> s;
    bool vis[MAXN];
    int ans = 0;
    fill(vis + 1, vis + n + 1, 0);

    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
        {
            continue;
        }
        else
        {
            vis[i] = true;
            s.push(i);
            while (!s.empty())
            {
                int c = s.top();
                s.pop();
                for (int j = 0; j < map[c].size(); j++)
                {
                    if (!vis[map[c][j]])
                    {
                        vis[map[c][j]] = true;
                        s.push(map[c][j]);
                    }
                }
            }
            ans++;
        }
    }
    return ans;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int s, e;
        cin >> s >> e;
        map[s].push_back(e);
        map[e].push_back(s);
    }

    int ans = count();
    if (ans != 1)
    {
        printf("Error: %d components", ans);
    }
    else
    {
        dijkstra(5);
        dijkstra(q.top());
        int p = 0;
        while (!q.empty())
        {
            int c = q.top();
            q.pop();
            if (p != c)
            {
                cout << c << endl;
            }
            p = c;
        }
    }

    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments