社区讨论

萌新刚学树,求助蜜汁RE

学术版参与者 3已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@locjqlul
此快照首次捕获于
2023/10/30 14:56
2 年前
此快照最后确认于
2023/11/05 02:12
2 年前
查看原帖
RT,按照老师的代码打的,结果CS Academy说是Segmentation Fault,求大佬帮帮忙qaq
CPP
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
struct node{
    ll to,nxt;
};
ll cnt=1;
vector<node> edge;
vector<ll> dis,vis,head;
template<typename T>
void fillvec(vector<T> &targ,T val,ll len){
    targ.clear();
    for(ll i=0;i<len;i++)targ.push_back(val);
}
void addedge(ll u,ll v){
    cnt+=1;
    edge[cnt].to=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void dfs(ll ind){
    vis[ind]=1;
    for(ll i=head[ind];i!=0;i=edge[i].nxt){
        if(not vis[edge[i].to]){
            dis[edge[i].to]=dis[ind]+1;
            dfs(edge[i].to);
        }
    }
}
void init(){
    fillvec<ll>(dis,0,100001);
    fillvec<ll>(vis,0,100001);
    fillvec<ll>(head,-1,100001);
}
ll n;
ll work(){
    init();
    cin>>n;
    for(ll i=0;i<n-1;i++){
        ll x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    dis[1]=1;
    dfs(1);
    static ll pos=1;
    for(ll i=1;i<=n;i++){
        if(dis[i]>dis[pos])pos=i;
    }
    fillvec<ll>(dis,0,100001);
    dis[pos]=1;
    dfs(pos);
    ll ans=-2147483648;
    for(ll i=1;i<=n;i++)ans=max(ans,dis[i]);
    return ans;
}
int main(){
    cout<<work();
    return 0;
}

回复

15 条回复,欢迎继续交流。

正在加载回复...