首页 > 其他分享 >计蒜客:网络延迟(DFS/BFS)

计蒜客:网络延迟(DFS/BFS)

时间:2024-11-08 19:07:53浏览次数:3  
标签:level int graph maximum dfs BFS DFS visited 计蒜客

 题目要求的是最远的两个节点的距离,即求树的直径(树中所有最短路径距离的最大值即为树的直径

 求树的直径有两种做法,两次bfs(或者dfs),另一种是用树形DP

本文用两次DFS实现

#include<bits/stdc++.h>
using namespace std;
int n, u, v;
vector<int> graph[50005];
vector<bool> visited(50005, false);
int origin;
void dfs(int p, int level, int & maximum) {
    visited[p] = true;
    bool isLeaf = true;
    for (auto i : graph[p]) {
        if (!visited[i]) {
            isLeaf = false;
            dfs(i, level + 1, maximum);
        }
    }
    if (isLeaf) {
        if (level > maximum) {
            origin = p;
            maximum = level;
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int maximum = INT32_MIN;
    
    //第一次dfs找到直径端点
    dfs(1, 0, maximum);
    
    //初始化dfs所需参数
    visited.clear();
    visited.resize(n + 5, false);
    maximum = INT32_MIN;
    dfs(origin, 0, maximum);
    cout << maximum;
}

 

标签:level,int,graph,maximum,dfs,BFS,DFS,visited,计蒜客
From: https://www.cnblogs.com/coderhrz/p/18535736

相关文章

  • OSS和FastDFS的区别
    FastDFS:FastDFS是一种开源的轻量级分布式文件系统,基于HTTP协议实现。具有高扩展性、高可用性和高稳定性。它解决了大容量文件存储和高效访问的问题,适合作为大容量文件的存储服务器。FastDFS通过文件系统集群,使得用户可以将文件存储在多台服务器上,而无需关心文件的实际存......
  • 103_api_intro_imagerecognition_pdfsplitter
    PDF分割拆分API数据接口文件处理,PDF高效的PDF分割工具,高效处理,可永久存储。1.产品功能高效处理大文件;支持多语言字符识别;支持formdata格式PDF文件流传参;支持设置每个PDF文件的页数;输出文件永久CDN存储;全接口支持HTTPS(TLSv1.0/v1.1/v1.2/v1.3);全......
  • Java深度优先搜索(DFS)算法实现
    标题:Java深度优先搜索(DFS)算法实现引言:深度优先搜索(Depth-FirstSearch,DFS)是一种常用的图遍历算法,它通过递归地遍历图中的每个顶点,来寻找特定的路径或解决某些问题。本篇博客将介绍如何用Java语言实现深度优先搜索算法。算法思想:深度优先搜索算法的基本思想是先访问一个......
  • HDFS 与 Swift:分布式存储系统的特点与适用场景
    在当今大数据时代,分布式存储系统扮演着至关重要的角色。其中,HDFS(HadoopDistributedFileSystem)和Swift是两种广泛应用的分布式存储系统。它们各自具有独特的特点和适用场景,下面我们就来详细了解一下。一、HDFS的特点和适用场景1.特点高可靠性:HDFS通过数据冗余存储来保证......
  • bfs(宽度搜索遍历)
    当边权为1时候,用bfs解决最短路问题题目:走迷宫给定一个 n×m的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该......
  • DFS(深度优先遍历)
    基础:排列数字给定一个整数 n,将数字1∼n 排成一排,将会有很多种排列方法。现在,请你按照字典序将所有的排列方法输出。输入格式共一行,包含一个整数 n。输出格式按字典序输出所有排列方案,每个方案占一行。数据范围1≤n≤7输入样例:3输出样例:12313221323......
  • 计蒜客:最短路简化版(BFS)
     在queue中用结束标识来节约队列空间。也可以用vector来实现队列,用[left,right]控制队列。1#include<bits/stdc++.h>2usingnamespacestd;3intn,m,c;4vector<int>graph[1005];5vector<bool>visited(1005,false);6vector<int>level(1005,0);7queu......
  • HDFS-HA搭建
    一、进行准备工作1、防火墙servicefirewalldstop2、时间同步yuminstallntpntpdate-us2c.time.edu.cn或者date-s201805033、免密钥(远程执行命令)在两个主节点生成密钥文件ssh-keygen-trsassh-copy-idipmaster-->master,node1,node2node1-->master,......
  • 计蒜客:互粉攻略(DFS/BFS)
     因为有重复数据,所以不得不等输入完以后再进行有向图的遍历。1#include<bits/stdc++.h>2usingnamespacestd;3intn,m;4set<int>graph[1005];5vector<bool>visited(1005,false);6vector<pair<int,int>>degree(1005,make_pair(0,0));//(入度,出度)......
  • 大数据导论及分布式存储HadoopHDFS入门
    思维导图数据导论数据是什么?进入21世纪,我们的生活就迈入了"数据时代"作为21世纪的新青年,"数据"一词经常出现。数据无时无刻的在影响着我们的现实生活什么是数据?数据又如何影响现实生活?数据:一种可以被鉴别的对客观事件进行记录的符号。简单来说就是:对人类的行为......