04-02 08:26 惠州学院 运营 发布于广东
关注
牛客小白月赛119 D
BFS，一开始把所有叶子存入队列，每次向内延伸。对于每个节点记录下延伸的轮数（它等于最近叶子节点的距离）
最终找出记录值最远的一些点即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> e[N];
int d[N],deg[N],vst[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin>>T;
while(T--)
{
int n; cin>>n;
for(int i=1;i<=n;i++)
{
e[i].clear();
d[i]=0; deg[i]=0; vst[i]=0;
}
for(int i=1,u,w;i<n;i++)
{
cin>>u>>w;
e[u].push_back(w);
e[w].push_back(u);
deg[u]++; deg[w]++;
}
queue<int> q;
for(int i=1;i<=n;i++)
if(deg[i]==1)
q.push(i), vst[i]=1;
while(!q.empty())
{
int x=q.front(); q.pop();
for(auto y:e[x])
{
if(vst[y]) continue;
d[y]=d[x]+1;
vst[y]=1;
q.push(y);
}
}
int mx=0;
for(int i=1;i<=n;i++)
if(deg[i]>1)
mx=max(mx,d[i]);
vector<int> ans;
for(int i=1;i<=n;i++)
if(deg[i]>1 && d[i]==mx)
ans.push_back(i);
cout<<ans.size()<<'\n';
for(auto x:ans) cout<<x<<' ';
cout<<'\n';
}
}
#刷题#
BFS，一开始把所有叶子存入队列，每次向内延伸。对于每个节点记录下延伸的轮数（它等于最近叶子节点的距离）
最终找出记录值最远的一些点即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> e[N];
int d[N],deg[N],vst[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin>>T;
while(T--)
{
int n; cin>>n;
for(int i=1;i<=n;i++)
{
e[i].clear();
d[i]=0; deg[i]=0; vst[i]=0;
}
for(int i=1,u,w;i<n;i++)
{
cin>>u>>w;
e[u].push_back(w);
e[w].push_back(u);
deg[u]++; deg[w]++;
}
queue<int> q;
for(int i=1;i<=n;i++)
if(deg[i]==1)
q.push(i), vst[i]=1;
while(!q.empty())
{
int x=q.front(); q.pop();
for(auto y:e[x])
{
if(vst[y]) continue;
d[y]=d[x]+1;
vst[y]=1;
q.push(y);
}
}
int mx=0;
for(int i=1;i<=n;i++)
if(deg[i]>1)
mx=max(mx,d[i]);
vector<int> ans;
for(int i=1;i<=n;i++)
if(deg[i]>1 && d[i]==mx)
ans.push_back(i);
cout<<ans.size()<<'\n';
for(auto x:ans) cout<<x<<' ';
cout<<'\n';
}
}
#刷题#
全部评论
相关推荐
查看15道真题和解析
美团工作强度 2450人发布