首页 > 代码库 > SDUT 3045-迷之图论(树的直径)
SDUT 3045-迷之图论(树的直径)
题目链接:点击打开链接
对于一棵无向树:
任意点出发,找到最远点,设这个为起点,从起点出发找到最远点为终点
这条路就是直径
两次BFS;
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 100010 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long using namespace std; vector <int> eg[maxn]; int dis[maxn],n; int bfs(int src) { memset(dis,0,sizeof(dis));dis[src]=1; queue <int> Q;Q.push(src);int E; while(!Q.empty()) { int u=Q.front();Q.pop();E=u; for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(!dis[v]) { dis[v]=dis[u]+1; Q.push(v); } } } return E; } int main() { int u,v; while(~scanf("%d",&n)) { if(n==1) { puts("1"); continue; } for(int i=1;i<=n;i++)eg[i].clear();--n; while(n--) { scanf("%d%d",&u,&v); eg[u].push_back(v); eg[v].push_back(u); } int ans=bfs(1); ans=bfs(ans); printf("%d\n",dis[ans]); } return 0; }
SDUT 3045-迷之图论(树的直径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。