我们的距离

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param n int整型 点的数量
     * @param edge Point类vector Point.x , Point.y 边所连接的两个点
     * @return long长整型vector
     */
    vector<int> G[100001];
    vector<int> s;
    vector<long> r;
    int DFS1(int u, int p, int d){
        int cnt=1;
        for(auto &v: G[u])
            if(v != p)
                cnt += DFS1(v, u, d+1);
        r[0] += d;
        s[u] = cnt;
        return cnt;
    }
    void DFS2(int u, int p, int n){
        for(auto &v: G[u]){
            if(p != v){
                r[v] = r[u] + n - 2*s[v];
                DFS2(v, u, n);
            }
        }
    }
    vector<long> solve(int n, vector<Point>& edge) {
        s.resize(n);
        r.resize(n);
        for(auto &e: edge){
            G[e.x-1].push_back(e.y-1);
            G[e.y-1].push_back(e.x-1);
        }
        DFS1(0, -1, 0);
        DFS2(0, -1, n);
        return r;
    }
};

void depth_first_search_algorithm(int* g,
                                  const int n,
                                  int cur,
                                  int prev,
                                  long* total,
                                  int step)
{
  int v;
  *total += step;    
  for (v = 1; v <= n; ++v)
    if (*(g + cur * (n + 1) + v) == 1 && v != prev)
      depth_first_search_algorithm(g, n, v, cur, total, step + 1);
}


long* solve(int n, struct Point* edge, int edgeLen, int* returnSize) {
  long* ans = (long*) malloc(n * sizeof(long));
  if (!ans) {
    *returnSize = 0;
    return NULL;
  }
  
  int g[n + 1][n + 1]; // 图的邻接矩阵表示法
  memset(g, 0x0000, sizeof g);
  
  int i, u, v; 
  for (i = 0; i < edgeLen; ++i) {
    u = edge[i].x, v = edge[i].y;
    g[u][v] = 1;
    g[v][u] = 1;
  }
  
  for (u = 1; u <= n; ++u) {
    long total = 0;
    depth_first_search_algorithm((int*) g, n, u, -1, &total, 0);
    *(ans - 1 + u) = total;
  }
  
  *returnSize = n;
  return ans;
}

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param n int整型 点的数量
   * @param edge Point类vector Point.x , Point.y 边所连接的两个点
   * @return long长整型vector
   */
  vector<long> solve(int n, vector<Point>& edge) {
    vector<long> ans(n);
    vector<vector<int>> g(n + 1);
    for (const auto& e : edge) {
      g[e.x].emplace_back(e.y);
      g[e.y].emplace_back(e.x);
    }
    
    for (int i = 1; i <= n; ++i)
      ans[i - 1] = bfs(g, n, i);
    
    return ans;
  }
  
private:
  int bfs(vector<vector<int>>& g, int n, int start) {
    deque<int> q{{start}};
    vector<int> seen(n + 1);
    seen[start] = 1;
    
    long total = 0;
    int steps = 0;
    while (not q.empty()) {
      size_t s = q.size();
      while (s--) {
        const int cur = q.front(); q.pop_front();
        total += steps;
        for (const int nxt : g[cur]) {
          if (seen[nxt]++) continue;
          q.emplace_back(nxt);
        }
      }
      ++steps;  
    } 
    
    return total;
  }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 点的数量
     * @param edge Point类一维数组 Point.x , Point.y 边所连接的两个点
     * @return long长整型一维数组
     */
    
    long count; // 记录某个点到其他点的距离
    
    // bfs 做法
    public long[] solve (int n, Point[] edge) {
        // write code here
        int[][] path = new int[n][n];
        
        for (Point e : edge) {
            path[e.x - 1][e.y - 1] = 1;
            path[e.y - 1][e.x - 1] = 1;
        }
        
        long[] result = new long[n];
        
        for (int i = 0; i < n; i++) {
            
            boolean[] visited = new boolean[n];
            
            visited[i] = true;
            
            count = 0;
            
            bfs(i, visited, path, 1);
            
            result[i] = count;
        }
        
        return result;
    }
    
    private void bfs(int node, boolean[] visited, int[][] path, int step) {
        
        ArrayList<Integer> nextNodes = new ArrayList<>();
        
        for (int i = 0; i < path[node].length; i++) {
            if (path[node][i] == 1 && !visited[i]) {
                nextNodes.add(i);
                visited[i] = true;
                count += step;
            }
        }
        
        for (int nextNode : nextNodes) {
            bfs(nextNode, visited, path, step + 1); // 随着递归的推进，距离越来越远，每次加一
        }
    }
}