Блог

Главная - Вопросы по программированию - Диаметр древовидного графа

Диаметр древовидного графа

#c #&raph #tree

#c #График #дерево

Вопрос:

Я спрашиваю себя, что не так с моим кодом для определения диаметра дерева:

(Под диаметром дерева я подразумеваю наибольшее расстояние между двумя узлами в этом древовидном графе)

 #include <iostream&&t;
#include <vector&&t;
#include <al&orithm&&t;
usin& namespace std;
#define MAXN 1000005
int n,a,b;
int dist[MAXN];
vector<int&&t; adj[MAXN];
vector<int&&t; ways;
void dfs(int U, int father){
    if(father==U){
        dist[U]=1;
    }
    else{
        dist[U]=1 dist[father];
    }
    for(int i=0;i<(int)adj[U].size();i  ){
        int V=adj[U][i];
        if(dist[V]==-1) dfs(V,U);
    }
}
void solve(int S){
    dist[S]=0;
    for(int j=0;j<(int)adj[S].size();j  ){
        int w=adj[S][j];
        dfs(w,w);
        int maxdist=0;
        for(int i=1;i<=n;i  ){
            if(dist[i]!=-1){
                maxdist=max(maxdist,dist[i]);
                dist[i]=0;
            }
        }
        ways.push_back(-maxdist);
    }
}
int main(){
    cin&&t;&&t;n;
    if(n==2) cout<<"1n";
    else{
    for(int i=1;i<=n;i  ){
      dist[i]=-1;
    }
    for(int i=1;i<n;i  ){
        cin&&t;&&t;a&&t;&&t;b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int vert;
    for(int i=1;i<=n;i  ){
        if((int)adj[i].size()&&t;1){
            vert=i;
            break;
        }
    }
    solve(vert);
    sort(ways.be&in(),ways.end());
    int ret=-(ways[0] ways[1]);
    cout<<ret<<"n";
    }
    return 0;
}

Для меня это звучит логично и очень процедурно, но я представил его онлайн-судье, и он не был принят. Что происходит?

Комментарии:

1. dfs может сорвать вершину со стека, если n он достаточно велик и дерево имеет правильную форму.

2. Какие ограничения устанавливает тест?

3. n должно быть меньше или равно 10 ^ 6 и больше или равно 2. Ограничение по времени составляет 5 секунд, что, по моему опыту, очень много при таких ограничениях

4. Во-первых, ваш метод ввода не гарантирует дерево. Это также может быть график с циклическими ссылками. Если это задано, то ваши методы не обрабатывают дерево с корнем, имеющим одного дочернего элемента. Вы используете ways[0] ways[1] , но второго способа может и не быть, поэтому UB.

Ответ №1:

Расстояние между двумя узлами в дереве измеряется с помощью A и B.

 distanceBetwwen_A_and_B = Distance A -&&t; CommonAncestor(A, B)
                          Distance B -&&t; CommonAncestor(A, B);

Таким образом, для данного узла-предка G он имеет максимальный радиус:

 Diameter(G)   = Distance_To_Furthest_Child(G-&&t;left)
                Distance_To_Furthest_Child(G-&&t;ri&ht)

Но один из его потомков может иметь больший радиус, чем он сам.

 Max_Diameter(G) = max(Diameter(G), Max_Diameter(G-&&t;left), Max_Diameter(G-&&t;ri&ht))

Исходя из этого, вы должны иметь возможность выполнять поиск в глубину и один обход для вычисления Max_Diameter (корня)

 struct Node
{
    Node*  l;
    Node*  r;
    int    maxD;
};

int findMaxD(Node* root)
{
    if (root == nullptr) {
        return 0;
    }
    calcMaxDiameter(root);
    return root-&&t;maxD;
}
/*
 * Sets the maxD value of a node
 * Returns the distance to the furthest decendant
 */
int calcMaxDiameter(Node* root)
{
    // If we fall of the end
    // The distance is zero.
    if (root == nullptr) {
        return 0;
    }
    int l_Distance = calcMaxDiameter(root-&&t;l);
    int r_Distance = calcMaxDiameter(root-&&t;r);

    // Calculate the preliminary Radius.
    root-&&t;maxD = l_Distance   r_Distance;
    if (root-&&t;l) {
        // If there is a left node see if it is bi&&er
        // than the current radius
        root-&&t;maxD = std::max(root-&&t;maxD, root-&&t;l-&&t;maxD);
    }
    if (root-&&t;r) {
        // If there is a ri&ht node....
        root-&&t;maxD = std::max(root-&&t;maxD, root-&&t;r-&&t;maxD);
    }
    // Return the distance to the furthest
    // ancestor. Add one for the distance from here
    // to the parent.
    return std::max(l_Distance, r_Distance)   1;
}