文章

9

粉丝

126

获赞

8

访问

25.1k

头像
BFS
P1841 南京理工大学机试题
发布于2023年3月14日 15:13
阅读数 2.7k

#include <bits/stdc++.h>
using namespace std;

typedef struct node{
	vector<int> edge;
	int deep;
	bool visit;
	
	node(){
		deep=0;
		visit=false;
	}
}node;

int main(){
	int m,n,u,v;
	scanf("%d %d",&n,&m);//m为指定结点 
	node nod[10000];
	queue<int> q;
	while(!q.empty()) q.pop();
	
	n--;
	while(n--){//建 图 
		scanf("%d %d",&u,&v);
		nod[u].edge.push_back(v);
		nod[v].edge.push_back(u);
	}
	
	//BFS求单源最短路径 
	int max=1;
	nod[m].deep=1;
	nod[m].visit=true;
	q.push(m);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<nod[now].edge.size();i++){
			if(!nod[nod[now].edge[i]].visit){
				nod[nod[now].edge[i]].visit=true;
				nod[nod[now].edge[i]].deep=nod[now].deep+1;
				if(max<nod[nod[now].edge[i]].deep) max=nod[nod[now].edge[i]].deep;
				q.push(nod[now].edge[i]);
			}
		}
	}
	cout<<max-1<<endl;
	
	
} 

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发